Often we wish to process a binary tree by visiting each of its nodes. And each time we visit a node, we might want to perform a specific action such as printing the contents of the node, adding/modifying the values in the node etc. Any algorithm which is used for visiting all the nodes of a binary tree in some order is called a tree traversal algorithm/routine.
Why Have Different Traversal Techniques?
Depending on the reason for traversing a binary tree, we might require that the nodes be visited in a particular order with some relationship. For example, if we wish to traverse all the nodes in a binary search tree, we would like to visit all the nodes in ascending order of their values. So we need to use a specific tree traversal technique which visits all the nodes in ascending order of their values. Similarly, if we wish to delete every node in the tree, we should visit the child nodes first and delete them before deleting the parent node. And this requires another kind of tree traversal technique.
The Basics
A binary tree has 3 components: The root node, left subtree and the right subtree. Each of left and right subtree’s can be thought of binary trees with different root nodes. For example, consider the binary tree shown below:
1
/ \
/ \
/ \
2 5
/ \ / \
3 4 6 7
The above binary tree has the root node as 1 with left subtree rooted at node 2 and right subtree rooted at node 5. Each of this subtrees can again have left and right subtrees. Some nodes might miss the left or right subtrees, like nodes 3, 4, 6, 7.
In all, there are 4 basic ways of traversing/visiting all these nodes in a binary tree. They are pre-order, in-order, post-order and level order tree traversals.
Note: Each traversal technique discussed here has a dedicated article under this section which contains implementations along with animations for a bigger binary tree.
Pre-order Traversal of a Binary Tree
In this tree traversal technique, at each level, the parent node is visited first, then all the nodes in the left subtree are visited and then all the nodes in the right subtree are visited. The slides given below simulates pre-order traversal of a simple binary tree with just 3 nodes.
In-order Traversal of a Binary Tree
In this tree traversal technique, at each level, all the nodes in the left subtree are visited first, then the parent node is visited and then all the nodes in the right subtree are visited. The slides given below simulates in-order traversal of a simple binary tree with just 3 nodes.
Post-order Traversal of a Binary Tree
In this tree traversal technique, at each level, all the nodes in the left subtree are visited first, then all the nodes in the right subtree are visited, and finally the parent node is visited. The slides given below simulates post-order traversal of a simple binary tree with just 3 nodes:
Level-order Traversal of a Binary Tree
In this tree traversal technique, all the nodes at the same level/depth are visited first before visiting the nodes present at the next level. For the example tree below, first node 1 is visited, then nodes 2,3 are visited and finally nodes 4,5,6,7 are visited.
Easier way of different traversal orders
Instead of recursively thinking about the order in which we need to visit nodes, there is an easier way of finding out the traversal order for each of pre-order, in-order and post-order tree traversals. The image below shows the process:
[Red dots (towards left of each node) correspond to visits in pre-order traversal. Green dots (towards bottom of each node) correspond to visits in In-order traversal and Blue dots (towards right of each node) correspond to visits in Post-order traversal.]
Let’s consider pre-order traversal for the above example. We start at the beginning of path drawn around the entire tree. As we move, whenever we come across a red dot closer to the path, we visit it. So the order of nodes in pre-order traversal is F B A D C E G I H.
Similarly let’s consider in-order traversal for the above example. We start at the beginning of the path drawn around the entire tree. As we move, whenever we come across a green dot closer to the path, we visit it. So the order of nodes in in-order traversal is A B C D E F G H I (Observe that the output is in proper order. Similarly when in-order traversal is done on binary search trees, the output will be in ascending or descending order).
Now let’s consider the post-order traversal for the above example. We start at the beginning of the path drawn arount the entire tree. As we move, whenever we come across a blue dot closer to the path, we visit it. So the order of nodes visited in post-order traversal is A C E D B H I G.
Image Source: Wiki
In the upcoming articles, we will go through each traversal technique in detail along with recursive and iterative implementations.