Sunny - 9 months ago 23

Ruby Question

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]

Your answer

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

Expected answer

[[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?

Answer Source

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.