Level Order Tree Traversal

Introduction

This is the third article in the Tree Traversals – Online Classes.

I have written many articles about non-linear data structures and their traversals. But the more you dive in you can find many more ways to traverse a tree. Here we try to solve the level order tree traversal for a binary tree and we will also try to figure out other variations of this traversal. This can we precisely extended for a n-ary tree as well.

Defining the problem

level order tree traversal

Let us consider the above tree, if we follow the blue line from root till end and print all the nodes, we will end up printing the level wise traversal.

So the level wise traversal will print 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.

Approach- Level Order Tree Traversal

As any other tree traversal can be solved either in recursive or iterative way, we can try the same here.

Iterative Way:

For a normal level wise traversal, we can start from the root and traverse till the height of the tree. Each iteration must print one level of the tree and hence the number of iterations would be equal to the height of the tree.

This can be done either by using the queue or the stack data-structure.
Using Queue

Running time of the above algorithm
If we carefully look at the above algorithm then we realize that we visit each node just once, the loop runs for N number of iterations where N is the number of nodes in the tree and in each iteration we perform a constant amount of work which is printing the current node’s data and pushing it’s two children.

Hence the running time would be O(N).

Using Stack

 

Running time of the above algorithm
As we can see there is a nested loop in the first section of the algorithm. The inner loop runs till the stack S1 is not empty and the outer loop also runs for the same amount of time.

In fact the inner loop is just to print one level at a time, which dictates the outer loop to run for O(H) time, where H is the height of the tree.
The inner loop runs for 2K times in each iteration of the outer loop where K is the current level.

The third loop also runs for 2k times in each iteration of the outer loop.

Hence, the running time of the algorithm is O(H) * O(2K) + O(2K) . This means the running time can be translated into
O(2K) (O(H) +1) or can be simply written as O(H) * O(2K)

This means that the running time depends on the height, so if the tree is skewed the running time will seem to increase. The maximum height of the tree can be N and in that case the width of the level would be just one, so the component 2K will reduce to a constant 1. Hence in all cases the running time would be O(2H).

Recursive Way:

I think that the recursive way of traversal is truly not recursive, it eventually relies on iterative steps over the height of the tree and the recursion can only be used in identifying the correct level and printing it.

Why can’t we just use recursion?
A recursion over a node in the tree will either traverse across the height at once and only stops at the leaf. If recursion is used here we end up printing the children before printing the siblings. So each call to recursion must print only one level and the correct one. So, we need three routines, one for printing the current level, which is recursive. The other routine will iterate over the levels and a third one to identify the height of the root.

Routine for Recursion

Running time of the above algorithm
As we can see the for loop runs for O(H) time where H is the height of the tree. Each of these H calls to the printCurrentLevel routine takes O(H) * O(2K) time as in the previous iterative way and the same justification holds true for this algorithm as well.

Routine for Finding Height of ROOT
You can find this code in one of my previous article “Operations in a binary tree.

Source Code

BinaryNode.java : The data-structure to represent a binary tree node.

Iterative Level Traversal Using Stack

Iterative Level Traversal Using Queue

Recursive Level Traversal

Create a sample Tree

Conclusion

Here we learnt different ways of traversing a binary tree in a level order. In the next article we will discover another way of traversal, the zig-zag or spiral traversal. Watch out for more…

For C source code you can visit Geeks for Geeks
Stay connected and stay Subscribed

  • Hengameh

    why I see & lt or & gt or & quot or & amp in codes? 🙁 and not the real characters …

    • Yes, the editor ruined it up. I will update. Thanks for pointing.

    • @Hengameh2015:disqus this is done. Hope you have a better experience now. 🙂

      • Holden

        Thanks 🙂