Binary Tree Traversal Techniques

(Indepth) Preorder, inorder and postorder tree traversals
🔗
(Basic) Preorder, Inorder & Postorder traversals
🔗
Pre-Order Tree Traversal
🔗
In-Order Tree Traversal
🔗
Post-Order Tree Traversal
🔗

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 of the nodes 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 3 ways of traversing/visiting all these nodes in a binary tree. They are in-order, pre-order and post-order tree traversals. This section contains articles for each traversal technique.

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:

TODO: Add level order traversal.

Easier way of traversing binary tree in any order

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 preorder, inorder and postorder 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

References