Lately, I’ve been trying to systematically organize tree traversal techniques in a structural way, and I realized that there were some missing concepts I took for granted for years (e.g. I used to assume that BFS is just a post-order traversal 😅) . Therefore, I’m writing this to help clear the confusion, and hopefully it will help others to have a better understanding of different traversal techniques, too.
Tree traversal is a special case of Graph traversal, and therefore, this techniques is also applicable to graph traversal. However, for simplicity, Binary Tree will be used a the study case throughout the article.
Basically, tree traversal can be grouped into 4 different traversing techniques:
- In-order traversal (a.k.a Depth First Search)
- Pre-order traversal
- Post-order traversal
- Level-order traversal (a.k.a Breath First Search)
This article will walk you through each of them with some example snippets Also, the implementations for the following techniques are mainly using stack (in-order, pre-order, and post-order traversal) and queue (level-order traversal) for traversing the entire tree.
For in-order, pre-order, and post-order traversal, the ordering mentioned in the name is the relative order of the current node and its children. For example, for the Binary Tree case, the ordering will be the order of the left child, current node, and the right child.
In-order traversal
In-order traversal is the traversing technique which traverses the tree on the exact relative order: left child -> current node -> right child. It’s also called Depth-First-Search (DFS) since it will have to visit it’s left nodes first before itself.
the left child, current node, and the right child.
Output of the above snippet:
[4, 2, 5, 1, 6, 3]Pre-order traversal
Similar to in-order traversal implementation, the only difference is that pre-order traversal has the ordering: current node -> left child -> right child
The output of the above snippet:
[1, 2, 4, 5, 3, 6]Post-order traversal
Similar to the above implementation, the only difference is the traversing order now is: left child -> right child -> root
The output of the above snippet is:
[4, 5, 2, 6, 3, 1]Level-order traversal
Unlike the other 3 techniques, level-order is probably the most intuitive and consumable traversal technique since it visits nodes level-by-level. That’s why it’s also called Breath First Search.
The output of the above snippet:
[1, 2, 3, 4, 5, 6]Hopefully this article could give a glimpse of different tree (or graph in general) traversing techniques. Also, the implementations are grouped in a generalized manner with the hope that traversing implementations will no longer be a blocker or a scary topic.
Happy coding!
