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
![Welp, Here's what the Fed *Just* Said [Fed FOMC Minutes]](/_next/image?url=https%3A%2F%2Fi.ytimg.com%2Fvi%2Fl8u23oq1E9E%2Fhqdefault.jpg&w=3840&q=75)
