ZIGZAG LEVEL ORDER TRAVERSAL BT

By: Saurav

2018-01-17 07:44:00 UTC

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

Example :
Given binary tree

3
/ \
9 20
/ \
15 7
return

[
[3],
[20, 9],
[15, 7]
]

InterviewBit

This problem is similar to the problem . We can use BFS similarly as we did in the level order traversal.
1. Use a buffer array to get each level.
2. The only difference being we need to alternate the order of the elements coming from buffer array while adding to the final array

lets see it in work:

 def zigzagLevelOrder(a)
        return [] unless a
        final_array = Array.new
        queue = Queue.new
        flag = true
        buffer_array = Array.new
        
        queue << a
        
        while !queue.empty?
        
            size = queue.size
            
            (size).times do
                element = queue.pop
                buffer_array << element.data
                queue << element.left if element.left
                queue << element.right if element.right
            end
            
            if flag
                final_array << buffer_array
                flag = false
            else
                final_array << buffer_array.reverse
                flag = true
            end
            
            buffer_array = Array.new
            
            
        end
        
        return final_array


    end

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