Sunny - 1 year ago 41
Ruby Question

# Level Order Traversal Binary Tree Issue

Problem statement:

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,null,null,15,7],
3
/ \
9  20
/  \
15   7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
``````

I've solved this with BFS, which is the most intuitive way to do this. However, I tried solving it another way and I'm unable to. Below is sample input / correct output vs. my output:

``````Your input
[3,9,20,null,null,15,7]

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

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

This is obviously because somewhere in the code [] is being returned, but here's my code:

``````def level_order(root)
return [] if root.nil?

arr = merge([level_order(root.left)], [level_order(root.right)]) #this returns an empty arr if both of those are nil..
arr.insert(0, [root.val])
end

def merge(arr1, arr2)
i = j = 0
while i < arr1.length && j < arr2.length
arr1[i] += arr2[j]
i += 1
j += 1
end
while j < arr2.length #check if any remaining elements in arr 2
arr1 << arr2[j]
j += 1
end

arr1
end
``````

In the above, I dealt with [] case by doing += instead of << and the merge function works if one arr is empty. The idea here is that I'm merging each level of the level order traversal for both left and right sides, then inserting the root at the beginning of the array.

I also considered that the root could be inserted as an empty array, but this can't be happening because I have an initial return statement that's called if root is nil. Any ideas?

It should be as simple as changing this

``````arr = merge([level_order(root.left)], [level_order(root.right)])
``````

To

``````arr = merge(level_order(root.left), level_order(root.right))
``````

However I would have written this slightly differently:

``````input = [3,9,20,nil,nil,15,7]

output = []
start  = 0
length = 1
while start < input.length do
output << input.slice(start, length).compact
start  += length
length *= 2
end

puts output.inspect
``````

This would avoid building a tree and would be more efficient than recursion.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download