4 Types of Tree Traversal Algorithms
Everything you need to know about tree traversal in 7 mins (with animations)
If you are a pro programmer or working in the Software Industry for years then this topic may seem to you very trivial. But the use-cases of such algorithms and the different variants of that may create confusion in beginners mind. Therefore, I attempted to put all you need to know about Tree Traversal in this single article (with animations).
“Animation can explain whatever the mind of man can conceive. This facility makes it the most versatile and explicit means of communication yet devised for quick mass appreciation.”― Walt Disney
This article is not only about theories around such algorithms, but you will also learn how to implement those algorithms through code.
Timeline
- Tree Data Structure
- Tree Traversal — Introduction
- Let’s dive in — Practical Guide
- Inorder Traversal
- Preorder Traversal
- Postorder Traversal
- Level Order Traversal
- Final Notes
1. Tree Data Structure
Before jumping into the tree traversal algorithms, let’s define Tree as a data structure first. That will help you to grasp the concepts in a meaningful way.
Tree is a hierarchical data structure which stores the information naturally in the form of hierarchy unlike linear data structures like, Linked List, Stack, etc. A tree contains nodes(data) and connections(edges) which should not form a cycle.
Following are the few frequently used terminologies for Tree data structure.
Node — A node is a structure which may contain a value or condition, or represent a separate data structure.
Root — The top node in a tree, the prime ancestor.
Child — A node directly connected to another node when moving away from the root, an immediate descendant.
Parent — The converse notion of a child, an immediate ancestor.
Leaf — A node with no children.
Internal node — A node with at least one child.
Edge — The connection between one node and another.
Depth — The distance between a node and the root.
Level — the number of edges between a node and the root + 1
Height — The number of edges on the longest path between a node and a descendant leaf.
Breadth — The number of leaves.
Sub Tree — A tree T is a tree consisting of a node in T and all of its descendants in T.
Binary Tree — is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.
Binary Search Tree — is a special type of binary tree which has the following properties.
- The left subtree of a node contains only nodes with keys lesser than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- The left and right subtree each must also be a binary search tree.
Note: For the sake of simplicity, we will use Binary Tree as an example to understand Tree Traversal Algorithms. But those algorithms can be generalised to other types of tree, as well.
2. Tree Traversal — Introduction
“In computer science, tree traversal (also known as tree search) is a form of graph traversal and refers to the process of visiting (checking and/or updating) each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited.” — Wikipedia
The definition of Wikipedia is self-explanatory to understand what Tree Traversal mean. But I want to elaborate more about the last line of the definition, which will help us to understand the types of Tree Traversal and how they are different.
Tree Traversal Algorithms can be classified broadly in the following two categories by the order in which the nodes are visited:
- Depth-First Search (DFS) Algorithm: It starts with the root node and first visits all nodes of one branch as deep as possible of the chosen Node and before backtracking, it visits all other branches in a similar fashion. There are three sub-types under this, which we will cover in this article.
- Breadth-First Search (BFS) Algorithm: It also starts from the root node and visits all nodes of current depth before moving to the next depth in the tree. We will cover one algorithm of BFS type in the upcoming section.
3. Let’s dive in — Practical Guide
It’s time to understand the concept in a practical way. I will use Java Programming Language to explain the code. But these algorithms can be coded in your preferred programming language the same way we will do in Java.
Below is the blueprint of our Node class which will act as the atomic member of the Tree Data Structure. We will call it TreeNode, which is holding data as an integer value, left and right children of the same type(TreeNode). You can use any other data structure to keep as data under the TreeNode.
4. Inorder Traversal
Inorder Traversal is the one the most used variant of DFS(Depth First Search) Traversal of the tree.
As DFS suggests, we will first focus on the depth of the chosen Node and then go to the breadth at that level. Therefore, we will start from the root node of the tree and go deeper-and-deeper into the left subtree with recursive manner.
When we will reach to the left-most node with the above steps, then we will visit that current node and go to the left-most node of its right subtree(if exists).
Same steps should be followed in a recursive manner to complete the inorder traversal. Order of those steps will be like (in recursive function)…
- Go to left-subtree
- Visit Node
- Go to right-subtree
Important Fact: Inorder Traversal of Binary Search Tree will always give you Nodes in sorted manner.
5. Preorder Traversal
Preorder Traversal is another variant of DFS. Where atomic operations in a recursive function, are as same as Inorder traversal but with a different order.
Here, we visit the current node first and then goes to the left sub-tree. After covering every node of the left sub-tree, we will move towards the right sub-tree and visit in a similar fashion.
Order of the steps will be like…
- Visit Node
- Go to left-subtree
- Go to right-subtree
6. Postorder Traversal
Similar goes with Postorder Traversal. Where we visit the left subtree and the right subtree before visiting the current node in recursion.
So, the sequence of the steps will be…
- Go to left-subtree
- Go to right-subtree
- Visit Node
7. Level Order Traversal
This is a different traversal than what we have covered above. Level order traversal follows BFS(Breadth-First Search) to visit/modify every node of the tree.
As BFS suggests, the breadth of the tree takes priority first and then move to depth. In simple words, we will visit all the nodes present at the same level one-by-one from left to right and then move to the next level to visit all the nodes of that level.
Implementation is slightly challenging here than the above three traversals. We will use a Queue(FIFO) data structure to implement Level order traversal, where after visiting a Node, we simply put its left and right children to queue sequentially.
Here, the order of adding children in the queue is important as we have to traverse left-to-right at the same level. Check out the below gist for more understanding.
8. Final Notes
Tree Traversal algorithms can be classified broadly in two categories:
- Depth-First Search (DFS) Algorithms
- Breadth-First Search (BFS) Algorithms
Depth-First Search (DFS) Algorithms have three variants:
- Preorder Traversal (current-left-right)— Visit the current node before visiting any nodes inside left or right subtrees.
- Inorder Traversal (left-current-right)— Visit the current node after visiting all nodes inside left subtree but before visiting any node within the right subtree.
- Postorder Traversal (left-right-current) — Visit the current node after visiting all the nodes of left and right subtrees.
Breadth-First Search (BFS) Algorithm has one variant:
- Level Order Traversal — Visit nodes level-by-level and left-to-right fashion at the same level.
Check out my Github Repository for detailed code.
Important Fact: There are other tree traversal algorithms that classify as neither Depth-First Search nor Breadth-First Search. One such algorithm is the Monte Carlo tree search, which concentrates on the analysis of the most promising moves, expanding the search tree based on a random sampling of the search space.
Opportunity for you…
Get access to my personal Java Collection Cheatsheet as a FREE Welcome Gift after joining my tribe. Get it now!
About the Author
Anand K Parmar is a Software Engineer, who loves designing and building Mobile Apps. He is a writer, publishing articles on Computer Science, Programming and Personal Finance. Connect with him on LinkedIn or Twitter. Check out his latest articles underneath.
