Binary Tree: Traversals
In this story, we familiarize ourselves with the different types of traversals. We cover each traversal in detail in separate stories. You can find the links at the end of the story.
What is traversal?
Traversal is iterating over the nodes in the tree exactly once. We can traverse the tree in the following two ways:
- We first cover the depth, i.e., depth-first traversal
- We first cover the breadth, i.e., breadth-first traversal
Depth-first Traversal
As we cover the depth-first, we iterate on the nodes along the path from the root to leaf nodes. Consider the following binary tree:
In the above tree, we have three leaf nodes: G, H, and F. Let’s iterate on nodes along the path from the root to leaf:
- Path A to G contains nodes A, B, D, and G.
- Path A to H contains nodes A, B, E, and H.
- Path A to F contains nodes A, C, and F.
The nodes visited are A, B, D, G, A, B, E, H, A, C, and F. There are some duplicate visits if we try visiting nodes along the path to leaf nodes, but for now, let’s assume we have a way to ignore these duplicates. We can say that we visited nodes A, B, D, G, E, H, C, and F.
If we change the order, we visit leaf nodes. We will get a different order. Suppose we visit the leaf nodes F, H, and C, then the nodes along the path from the root to leaf are given below:
- Path A to F contains nodes A, C, and F.
- Path A to H contains nodes A, B, E, and H.
- Path A to G contains nodes A, B, D, and G.
The nodes visited are A, C, F, A, B, E, H, A, B, D, and G. Removing the duplicates, we have nodes A, C, F, B, E, H, D, and G.
Pre-order Traversal
The pre-order traversal is a kind of depth-first traversal. We perform the following steps:
- Access the node
- Recursively traverse the node’s left subtree in pre-order
- Recursively traverse the node’s right subtree in pre-order
The pre-order traversal visits the nodes A, B, D, G, E, H, C, and F.
In-order Traversal
The in-order traversal is a kind of depth-first traversal. We perform the following steps:
- Recursively traverse the node’s left subtree in in-order
- Access the node
- Recursively traverse the node’s right subtree in in-order
The in-order traversal visits the nodes D, G, B, H, E, A, C, and F.
Post-order Traversal
The post-order traversal is a kind of depth-first traversal. We perform the following steps:
- Recursively traverse the node’s left subtree in post-order
- Recursively traverse the node’s right subtree in post-order
- Access the node
The post-order traversal visits the nodes G, D, H, E, B, F, C, and A.
Breadth-first Traversal
We traverse the tree level-by-level because we want to cover the breadth-first. We first traverse all the nodes in a level and then traverse the next level guaranteeing a unique visit order. This traversal is also called level-order traversal.
Consider the following binary tree:
The level-order traversal on the above tree is:
- We visit node A to complete level 0.
- We visit nodes B and C to complete level 1.
- We visit nodes D, E, and F to complete level 2.
- We visit nodes G, and H to complete level 3.
There are no duplicate visits because we are iterating on nodes level-by-level. We have a unique level-order visit on the tree A, B, C, D, E, F, G, and H.
Detailed Stories on Traversals
- The pre-order traversal.
- The in-order traversal.
- The post-order traversal.
- The level-order traversal.
