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

About chesterli0130

Think more
This entry was posted in Trees & Graphs. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s