2017-12-31 10:17:00 UTC
Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
Given binary tree
return its level order traversal as:
Also think about a version of the question where you are asked to do a level order traversal of the tree when depth of the tree is much greater than number of nodes on a level.
This is a good one. It's a basic tree problem but in my first attempt, I implemented it wrong. I used BFS and started adding all children one by one but in level order traversal, the array as required here at each level is a single array for all the children on one level.
The trick is to add all the data at one level in a loop inside the BFS iteration loop
1. For the single root, you will add root data, iterate through all the elements in the queue(only 1) and pop it, and add its two children in the array.
2. Now the queue has two elements.Make a new buffer array. go through each element in the queue, pop them one by one and add the values to the buffer array. Add their children to the queue (4 total). Add this buffer array to the final array.
3. Go through the 4 children, pop them one by one, add the values to a new buffer array and add their children (8 total) to the queue.
Hope you get the gist! (You need an extra loop variable to store the number of children in the last level and once you have popped all of them and stored the value in an array, you need to update the size to the next level children number)
**Remember! In BFS, you don't need recursion. It's iteration through queue elements**
Let's get to coding now:
def levelOrder(a,queue = Queue.new, final_array = Array.new) return  if a == nil queue << a while !queue.empty? size = queue.size i = 0 buffer_array = Array.new while i < size node = queue.pop buffer_array << node.data queue << node.left if node.left != nil queue << node.right if node.right != nil i += 1 end final_array << buffer_array end return final_array end
Owned & Maintained by Saurav Prakash
If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :)