Saturday, July 26, 2014

Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]
 
Solution:
 
This is solved using BFS. One way to print in levels is to keep 
2 queues.Current queue and a nextlevel queue. nextlevel queue 
has left and right children of the node popped from current 
queue.Once the current queue is empty we swap current queue 
with nextlevel queue.Another solution is to use only 1 queue and
keep track of level using variables. nodesInCurrentLevel 
nodesInNextLevel.
 
Here is the source code.  


Do comment if you would like to add something to it.

No comments:

Post a Comment