TreeTraversal Algorithms
Common ways for traversing a binary tree
Tree traversal is a form of graph traversal, its the process of visiting each node in a data structure in order to retrieve data. Tree traversal algorithms are classified by the order in which the nodes are visited, here ill go over Preorder traversal, Inorder traversal, Postorder traversal, level order traversal.
Preorder traversal begins by visiting the root of the tree and then recursively processing all the subtrees by first traversing the left tree and then traversing the right tree.
In the above image, if we were to use preorder traversal we would begin at node 1, move left to node 2, again move left to node 4, and then again move left to node 8. now that we are at a node that no longer points to another node on the left, we move back up to node 4 and then traverse right to node 9. the left subtree will always be visited first until completely visited, then it will return to the nearest value that has a right tree that has yet to be visited. when we eventually reach the root node again, node 1, we will pass down to the right side and process the right tree again, still moving left before right. Let it be noted that each time we move to a different node we will collect the output of the node.
In-order tree traversal begins by traversing left, then visiting a node, then traversing right.
In this example, we will begin at node F and then move down to node b, since we are using in-order traversal we will not collect the output of node B. we now move down to node A, since there is no longer a left subtree of A we will record the output of node A. since there is no right subtree we will move back up to Node B. Since there is no longer a left subtree that has not been traversed, we will collect the output of B and traverse the right subtree. this pattern is followed in the right subtree of node B, going from Node D to Node C, collecting the output, then returning to D, collecting the output then going down the right tree.
Postorder tree traversal follows the three steps of traversing left, traversing right, then visiting the node.
using the same node tree. beginning at node F, we traverse to Node B, then traverse to node A. we then try to traverse left and right. since there are no subtrees to traverse we move back up to Node B collecting node A’s output, and traverse to the right subtree node D. from D we traverse left to node C, then as there are no subtrees, we collect node C’s output and then we traverse back to D and then move to E. from here we traverse back to node D, and B, collecting their outputs along the way. data collected in this tree would go in order node[A, C, E, D, B, H, I, G, F]
Level order tree traversal works a bit differently as it will not work recursively, instead, we will be enqueuing and dequeuing iteratively.
Here we start at F add it to our queue and collect its value removing it from the queue. we then add B and G to our queue. from here we will collect B’s output and remove it from the queue. From B we will add A and D to the queue. currently, in our queue, we have an array [G, A, D]. we will now remove G from our queue and record its output while attempting to add its children, so we will add I to our queue. currently, our queue is [A, D, I], from here we can see that we enqueue children then we dequeue them as soon as we are done enqueuing them. recording their values as we finish recording their children.
Two important tree traversal algorithms include Breadth-first traversal (BFT) and Depth-first Traversal(DFT). post, in order, and preorder are more similar to depth-first traversal while level order is more similar to breadth-first traversal. I will go into detail on these two traversal algorithms in future posts. I hope that this gives you a quick understanding of how to navigate a binary tree data structure!
