Level Order Binary Tree Traversal

Given a binary tree, print out the tree in level order.
Output a newline after the end of each level.

  3
 / \
9   20
   /  \
  15   7

Output:
3
9 20
15 7

Thoughts:
We can use BFS to solve this problem.
For each node, first the node is visited and then it’s child nodes are put in a FIFO queue.

printLevelorder(tree)
1) Create an empty queue q
2) Enqueue root
3) Loop while queue is not empty
a) Node n = dequeue q, print n->data.
b) Enqueue n’s children (first left then right children) to q

For printing nodes by level, we can use two extra counting variables which keep tracks of the number of nodes in the current level and the next level.
When the number of nodes in current level is zero, then the current level has ended.

Code:

public void traversalByLevel(TreeNode root){
    LinkedList queue = new LinkedList();
    int numNextLevel = 0;
    int currentLevel = 1;

    queue.add(root);

    while(!queue.isEmpty()){
        TreeNode n = queue.remove();
        currentLevel--;
        System.out.print(n.data+" ");
        if(currentLevel == 0){
            System.out.print("\n");
            currentLevel = numNextLevel;
            numNextLevel = 0;
        }

        if(n.left != null){
            queue.add(n.left);
            numNextLevel++;
        }
        if(n.right != null){
            queue.add(n.right);
            numNextLevel++;
        }
    }
}

Time Complexity: O(n) where n is number of nodes in the binary tree

References:
http://www.leetcode.com/2010/09/printing-binary-tree-in-level-order.html
http://www.geeksforgeeks.org/archives/2686

Advertisements