Sunny Sunny - 9 months ago 23
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]

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.