Level-order traversal of a Binary Tree

Level order traversal is different from other more common types of tree traversal algorithms such as in-order, pre-order or post-order. Level order traversal visits the nodes level by level. Once it’s done with the root (level 0) it moves to level 1, then to level 2, e.t.c. Perhaps the two most major differences between level-order traversal and the other 3 algorithms are that:

  1. It is an iterative algorithm
  2. It makes use of an extra data structure, a FIFO queue.

The reason why we need to use a queue is because we have no easy way of travelling backwards in a tree.

For example, in the following tree, if we are at the node with value 2, it may be easy to go to node number 5, but what about node 8?

(Node-2 and Node-8 belong to different subtrees, accessing one from the other requires going backwards)

The only node that connects these two nodes (formally called the Lowest Common Ancestor) is node number 6, the root of the tree. Now imagine a very deep tree with countless of leaves and the problem gets downright impossible.

That’s where the queue comes into play. The algorithm is pretty simple.

  1. Push the root into the queue
  2. While the queue is not empty
    1. Pop a node from the queue (Remember a queue works in a First-In First-Out way)
    2. Do something with its data
    3. Push its children into the queue
  3. By the time the queue is empty, the algorithm will have visited all nodes

Let’s apply level-order traversal to the above tree to visit and print all of its nodes. We start with a queue that only contains the root of the tree.

Queue: node-6

First loop (Level 0)

We begin by taking the first element out of the queue, which of course is the root of the tree. We print its value to the output and push its children into the queue

Queue: node-6, ode-4
Output: 6

Second loop (Level 1)

We take node-9 out of the queue, print its value and push its two children into the queue

Queue: node-4, node-2, node-5
Output: 6, 9

Third loop (Level 1)

We take node-4 out of the queue, print its value and push its right child into the queue

Queue: node-2, node-5, node-8
Output: 6, 9, 4

Fourth loop (Level 2)

We take node-2 out of the queue. Node-2 does not have any children so nothing gets pushed to the queue. We just print “2”.

Queue: node-5, node-8
Output: 6, 9, 4, 2

Fifth loop (Level 2)

We take node-5 out of the queue. Node-5 has no children nodes so we just print its value and move on

Queue: node-8
Output: 6, 9, 4, 2, 5

Sixth loop (Level 2)

We take node-8 out of the queue. Node-8 has no children nodes, so we print “8” and then notice that the queue is empty. So the sixth loop is the final one and we’ve managed to print all elements of the tree in a level-order from left to right.

Output: 6, 9, 4, 2, 5, 8

Now to the C++ implementation of the algorithm:

Each node is described by the following struct:

And here’s the levelOrderTraversal function

The C++ Standard Library provides a FIFO queue out of the box accessible to you by including the header. However you can still use a custom implementation of it if you like .

Post-order Traversal of a Binary Tree in C++

If you know about pre-order traversal you know that it visits the root first and the subtrees later. If you know about in-order traversal you know that it visits the nodes in-order (duh), first the left subtree , then the root and finally the right subtree. The remaining combination is to operate on the root when you’re done with the subtrees. That’s what post-order traversal does.

Let’s see an example of printing all the nodes of a tree using post-order traversal:


Starting from the root the post-order traversal algorithm will visit the left subtree, the right subtree and then return to the root node when it’s done.

Output so far:

We visit the left subtree on node-9 and move on its own subtrees until we find the tree’s leaves.

Output so far:

When we reach node-2 there are no left and right subtrees so we print it

Output so far: 2

Same way with node-5

Output so far: 2, 5

We return to node-9 and since we’re done with its subtrees we print the value 9

Output so far: 2, 5, 9

Back to node-6. We haven’t yet visited its right subtree so on we go

Output so far: 2, 5, 9

Node-4 has no left subtree, so we visit its right-hand one.

Output so far: 2, 5, 9

We visit node-8’s left and right subtrees which are empty and then return to node-8 and print its value

Output so far: 2, 5, 9, 8

Now that we’re done with node-4’s subtrees we print its value

Output so far: 2, 5, 9, 8, 4

We’re done with both subtrees of our tree’s root, node-6. It’s time to print its value too.

Output so far: 2, 5, 9, 8, 4, 6

And that’s it. We’ve traversed the tree In a post-order fashion and have printed its nodes.

The algorithm that achieves that in C++ is the following: