00:05in this video we show you how to trace

00:09three slightly different variations of a

00:11tree traversal algorithm in order to

00:14traverse the contents of a tree in a

00:16pre-order post order and inorder fashion

00:21when a binary tree is been constructed

00:23there are three very different ways of

00:25traversing it these are known as

00:27preorder traversal inorder traversal and

00:30post order traversal as important for

00:33the exam so in the difference between

00:35three each one will chuck out the data

00:38from the binary tree in a different

00:40order now for all examples let's

00:43remember that the import order is the

00:45same it went to d'origine alphabetically

00:48so Dave came in first as the route

00:50Craig was alphabetic less than Dave who

00:52went left some came next had to go right

00:55Cowell was next came in after Dave after

00:59Craig goes down here and then finally

01:02mark was alphabetically greater than

01:04Dave but alpha T less than Sam the order

01:08was different the important thing to

01:10note through work through these examples

01:11is the only difference between pre-order

01:14in-order and post-order traversal is the

01:17point to which the root is visited so

01:20let's look at pre-order traversal

01:21carefully this is known and for the exam

01:25should be remembered as the top down

01:27traversal method it encounters all of

01:30the routes before encountering all of

01:32the leaves so we visit the root and we

01:37output Dave we then traverse left this

01:41now becomes on you tree and this is the

01:45root of our new subtree we visit it and

01:48we output Kraig and we traverse left

01:51we now hit this subtree this becomes an

01:54entirely new sub tree of which cow is

01:56the root we visit the root and we output

01:58Carol we traverse left

02:01we can we Traverse right we can't we

02:05come up with outputted this we come up

02:07again yeah well we've all outputted this

02:10so we Traverse right this is now our new

02:14sub tree this becomes the root we visit

02:16the root and outputs

02:18which reverse left which we can this

02:21becomes a new subtree this therefore

02:23becomes our root and we was at the root

02:25and we have put mark in the exam you

02:28should think about placing your pointers

02:32or in this case our dots to the left of

02:35the values and then if you draw a line

02:37around you output each value as you

02:40visit the dot on the left so we've

02:43passed the left of Dave we output it

02:45we've passed the left of craig-carroll

02:47we come up to the right and as we pass

02:49the left of Sam we output and output the

02:52left of mark with in order traversal we

02:59retrieve the data according to its

03:01inherent sequence now we'll go over that

03:03again in a second what's important here

03:05is we traverse left first and we visit

03:08the root node second to help with this

03:11type of traversal you should think of

03:13placing the dots or markers below the

03:16values and the only output when we hit

03:18them so we traverse left

03:21which reverse left and as we come under

03:25cow and pass it we hit or dot visiting

03:29although an output we then come back up

03:32we are underneath Craig so we output

03:35well underneath Dave so we output which

03:42this becomes a route where traveling

03:44underneath mark so we output trail back

03:47up and we're underneath Sam so we output

03:50you'll notice that in order traversal is

03:53very very useful it's actually output

03:57the data from this binary search tree in

04:00the alphabetic order so it came in as

04:04Dave Craig sam Carol and Mark got sorted

04:07alphabetically and when we use in order

04:09traversal the values have come out in

04:12alphabetic order the final traversal

04:17method is post order traversal here we

04:21visit the root last this is known as a

04:25bottom-up traversal it encounters all

04:28the leaves before encountering all the

04:31again in the exam if you place your dot

04:34or your marker to the right of each

04:36value and then again follow around

04:39output each value as we pass the marker

04:42you'll be performing a post order

04:44so which reverse the left subtree we

04:48traverse the left subtree this is the

04:51root of this bottom subtree and as we

04:53come around it to the right we output

04:56cow we come up we output Craig we're

05:00underneath Dave so we don't output this

05:02and as we can see here we're required to

05:05traverse to the right and to the left

05:07this is the route of the current subtree

05:09and as we walk around to the right of it

05:11we output it we output Sam we come back

05:16up and we output Dave as mentioned the

05:21three different types of reversals are

05:22very very similar here's our example

05:25pseudocode the only difference is that

05:28we are visiting the roots at a different

05:31point and if we place the markers to the

05:35left underneath and to the right you

05:37literally can follow with a pen around

05:40in the exam and output the values as you

05:43hit your markers and you will get the

05:45correct output for the traversal method

05:48you're trying to use