## 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

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**

1 2 3 4 5 6 7 8 |
Q.add(root) while Q is NOT EMPTY T <- Q.remove print T.data if T.left Q.add(T.left) if T.right Q.add(T.right) |

**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**

1 2 3 4 5 6 7 8 9 10 11 12 13 |
S1, S2 ; S1.push(root) while S1 OR S2 is not empty while S1 is not empty T <- S1.pop if T.left print T.left.data S2.push(T.left) if T.right print T.right.data S2.push(T.right) while S2 is not empty S1.push(S2.pop) |

**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 ** 2 ^{K} ** times in each iteration of the outer loop where K is the current level.

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

Hence, the running time of the algorithm is ** O(H) * O(2 ^{K}) + O(2^{K}) **. This means the running time can be translated into

**O(2**or can be simply written as

^{K}) (O(H) +1)**O(H) * O(2**

^{K})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 2^{K} will reduce to a constant 1. Hence in all cases the running time would be O(2^{H}).

### 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**

1 2 3 4 5 6 |
printCurrentLevel(node, level) if level = 0 AND node is NOT NULL print node.data else printCurrentLevel(node.left, level-1) printCurrentLevel(node.right, level-1) |

**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(2^{K}) 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public class BinaryNode { BinaryNode left; BinaryNode right; Integer data; public BinaryNode(BinaryNode left, BinaryNode right, Integer data) { super(); this.left = left; this.right = right; this.data = data; } @Override public String toString() { return "BinaryNode [data=" + data + "]"; } } |

**Iterative Level Traversal Using Stack**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
public void levelTraverseStackIterative(Stack S) { BinaryNode node = S.pop(); if (node == null) return; Stack O = new Stack(); O.push(node); System.out.print(node.data); System.out.print(" "); while (!S.isEmpty() || !O.isEmpty()) { while (!O.isEmpty()) { BinaryNode pop = O.pop(); if (pop.left != null) { System.out.print(pop.left.data); S.push(pop.left); } System.out.print(" "); if (pop.right != null) { System.out.print(pop.right.data); S.push(pop.right); } System.out.print(" "); } while (!S.isEmpty()) { O.push(S.pop()); } } } |

**Iterative Level Traversal Using Queue**

1 2 3 4 5 6 7 8 9 10 |
public void levelTraverseQueueIterative(Queue Q) { while (!Q.isEmpty()) { BinaryNode node = Q.poll(); System.out.print(node.data + " "); if (node.left != null) Q.add(node.left); if (node.right != null) Q.add(node.right); } } |

**Recursive Level Traversal**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
public void recursiveLevelTraversal(BinaryNode node) { int h = 5; for (int i = 0; i < h; i++) { printCurrentLevel(node, i); } } public void printCurrentLevel(BinaryNode node, int level) { if (level == 0 && node != null) System.out.print(node.data +", "); else { printCurrentLevel(node.left, level - 1); printCurrentLevel(node.right, level - 1); } } |

**Create a sample Tree**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
public static BinaryNode createTree() { BinaryNode n31 = new BinaryNode(null, null, 31); BinaryNode n30 = new BinaryNode(null, null, 30); BinaryNode n29 = new BinaryNode(null, null, 29); BinaryNode n28 = new BinaryNode(null, null, 28); BinaryNode n27 = new BinaryNode(null, null, 27); BinaryNode n26 = new BinaryNode(null, null, 26); BinaryNode n25 = new BinaryNode(null, null, 25); BinaryNode n24 = new BinaryNode(null, null, 24); BinaryNode n23 = new BinaryNode(null, null, 23); BinaryNode n22 = new BinaryNode(null, null, 22); BinaryNode n21 = new BinaryNode(null, null, 21); BinaryNode n20 = new BinaryNode(null, null, 20); BinaryNode n19 = new BinaryNode(null, null, 19); BinaryNode n18 = new BinaryNode(null, null, 18); BinaryNode n17 = new BinaryNode(null, null, 17); BinaryNode n16 = new BinaryNode(null, null, 16); BinaryNode n15 = new BinaryNode(n30, n31, 15); BinaryNode n14 = new BinaryNode(n28, n29, 14); BinaryNode n13 = new BinaryNode(n26, n27, 13); BinaryNode n12 = new BinaryNode(n24, n25, 12); BinaryNode n11 = new BinaryNode(n22, n23, 11); BinaryNode n10 = new BinaryNode(n20, n21, 10); BinaryNode n09 = new BinaryNode(n18, n19, 9); BinaryNode n08 = new BinaryNode(n16, n17, 8); BinaryNode n07 = new BinaryNode(n14, n15, 7); BinaryNode n06 = new BinaryNode(n12, n13, 6); BinaryNode n05 = new BinaryNode(n10, n11, 5); BinaryNode n04 = new BinaryNode(n08, n09, 4); BinaryNode n03 = new BinaryNode(n06, n07, 3); BinaryNode n02 = new BinaryNode(n04, n05, 2); BinaryNode n01 = new BinaryNode(n02, n03, 1); return n01; } |

## 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