Category Archives: Traversal

Level order traversal of the binary tree from the bottom

Given a binary tree, how do we print the nodes in level order starting from the bottom.

For example for the following tree, the output should be 2 3 1

    1
  / 
 2    3

An obvious solution is to first find the maximum levels of the tree. we can print the nodes from maximum level to minimum level. This is not so efficient, because to print each level we need to traverse all the nodes.

Another solution is that we can modify the level order traversal. We need an additional stack to store the nodes. Instead of printing the values of the nodes as soon as they are deleted from the queue, we can add them to stack. Later, we can pop the elements from the stack and print them. This will print the elements in reverse level order.

Here is the C++ code for the second approach.


Traversals of a binary tree

Traversal algorithms of non-linear data structures like trees are designed to visit/print all the elements in that structure.

There are three main traversals of the binary tree. Namely

  • In-order traversal
  • Post-order traversal
  • Pre-order traversal
In addition to these, there are inverses of the above algorithms, and there is a level order traversal.

In this post we will see the three main traversal algorithms mentioned above. All of these are defined as recursive algorithms.
In In-order traversal, we first visit the left sub-tree, then root, and then the right sub-tree.
In Post-order traversal, we first visit the left sub-tree, then the right sub-tree, and then the root.
In Pre-order traversal, We first visit the root, then visit the left sub-tree and then visit the right sub-tree.

For example consider the simple  3 node binary tree

In-order traversal: B  A  C
Post-order traversal: B  C  A
Pre-order traversal: A  B  C

To consider a bigger example, take the following binary search tree and it’s traversal sequences for the three algorithms.

In-order: 1  2  3  4  5  6  7  8

Post-order: 1  2  4  3  7  6  8  5
Pre-order: 5  3  2  1  4  8  6  7 
The in-order traversal of the binary search tree always produces the sorted order of it’s elements.

Here is the C++ code for all the traversals.