Algorithm Talk! Day 4: Depth First Tree Traversal
So I imagine that we’re getting a little tired of talking about sorting algorithms at this point, having already three of them over the past month. So I figured now we can start talking about search algorithms. I will wait until next time to go into specific search algorithms, but in the meantime I will be giving a basic overview of Tree Traversal and briefly describe how each work.
What is Tree Traversal?
While so far in our sorting algorithms, we’ve found that we’ve mostly been working with Array or List data structures. With Tree traversal, we’re looking specifically at the Tree data structure. Since you will most commonly find yourself working with and using Binary Trees, that is each node has 0, 1 or 2 child nodes, I will be mostly discussing these searches in the context of them. Do note however, that Trees with more than 2 children exist.
Traversals are generally categorized into Depth-First and Breadth-First. This week’s discussion will focus on the former, and we will be revisiting the latter at a later date. All traversals involve ‘visiting’ each node in the tree which in terms of traversal means accessing the data at that node, assuming that we are not utilizing any sort of parallel computation like multi-threading. In additional to the fact that trees, unlike linear data structures, can have more than one possible ‘next’ node, it is necessary to store nodes that need to be visited at a later point in our search. Typically, a stack or a queue is used to store these nodes. For the sake of brevity though, I will first be discussing this at a higher level, and then will go into actual implementation.
Pre-Order Traversal
Pre-Order Traversal, otherwise known as NLR (Node-Left-Right), begins with accessing data from the Parent, then the Left child of the parent, then the Right child of the parent. It is recursively called on the left and right children of the root node until the end of the tree is reached. In our example:
Step 1) We visit node A, the root node, first
Step 2) We then visit node B, the left child of node A.
Step 3) We check if node B has a left child. It does, so this means that after accessing node B, we visit its left child, node D. This repeats until we reach the end of the left children.
Step 4) We check if node D has a left child. It does not, so this means we check if node D has a right child. It also does not, so this means we are finish with the tree rooted at node D.
Step 5) We now check if node B has a right child. It does, and since we already visited node B, we go straight to node E.
Hopefully you can start to see the order in which Pre-Order Traversal visits these nodes. The steps above continue until we reach the last child without children of the tree. The full traversal illustration is below:
In-Order Traversal (and Reverse In-Order Traversal)
In-Order Traversal, otherwise known as LNR (Left-Node-Right), begins with first visiting the Left child, then visiting its parent, then visiting the Right child. This is recursively called until we reach the right most branch of the tree. For the Reverse In-Order Traversal, simply reverse the steps so that it is Right-Node-Left. The result is the exact reverse, as the name implies, of In-Order Traversal.
This break-down is only for In-Order, though I will include a Reverse In-Order traversal illustration at the end of this section:
Step 1) We check if node A has a left child. It does, so we move to node B. We repeat this check for left child until the node we are on does not have a left child. This is node D in our example.
Step 2) We access the data in node D, then we access the data in its parent node, B.
Step 3) We check if node B has a right child. It does so we move to node E, and then we repeat step 1 until we reach the end of node E’s left children, in this case node H.
Step 4) We access node H, and then we access the data in its parent node, E.
Hopefully you can start to see the order in which In-Order Traversal visits these nodes. The steps above continue until we reach the last child without children of the tree. The full traversal illustration is below:
Post-Order Traversal
Post-Order Traversal, as you might have guessed at this point, also known as LRN (Left-Right-Node), begins with visiting the left child of the parent, then the right child of the parent, and then finally the parent itself. It is, as the other traversals have been, called recursively until we reach the root node of the overall tree. In our example:
Step 1) We check if Node A has a left child. It does so we move to node B, repeating this until we reach a node that does not have a left child, in this case node D.
Step 2) We access the data in node D, then we check if the parent of node D, node B, has a right child. It does so we move to node E, and from here we repeat Step 1, until we reach the end, which is node H.
Step 3) We access the data in node H, then we check if the parent of node H, node D, has a right child. It does so we move to node I, and see that it does not have a left child or a right child.
Step 4) We then access the data in node I, then we access its parent node, node H.
Hopefully you can start to see the order in which Post-Order Traversal visits these nodes. The steps above continue until we reach the root node the tree. The full traversal illustration is below:
When to use Depth First Tree Traversal?
The usage of Depth First Tree Traversal is usually found in situations where you need to explore the entire tree and if you expect that the goal or solution is further away than the starting node. Since we haven’t yet talked about Breadth First Tree Traversal, it is difficult to make a full analysis on when to use Depth First Tree Traversal, as most often you’d find yourself deciding between Depth First or Breadth First. To that end, just keep in mind for the time being that Depth First Tree Traversal uses less memory than Breadth First on average, and is more suited for ‘deeper’ (more levels) trees.
