GRAPH ALGORITHM: LEVEL ORDER TRAVERSAL

By: Saurav

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).

Example :
Given binary tree

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

[
[3],
[9,20],
[15,7]
]
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.

InterviewBit

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

Looks pretty good to me.


Let me know what you think!
twitter: sprakash24oct
linkedin

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 :)