Question: You are given 2 number streams. You need to find whether they will create the same BST or not.

Example:
Array1:10 5 20 15 30
Array2:10 20 15 30 5
Result: True

Array1:10 5 20 15 30
Array2:10 15 30 20 5
Result: False (see corresponding trees below)



Answer:

Method of building a BST from an incoming stream is like below:

  1. Make first element as root.
  2. If current element is smaller then root -> insert in left subtree.
  3. If current element is greater then root -> insert in right subtree.
  4. If current element is equal to root -> skip (or as pre-decided)
  5. While inserting in left and right subtree, follow above steps recursively.

So in above question, we have to check top-down if all the subtrees are identical or not. For that, we should follow below steps:

  1. Check if stream is finished if yes -> return false
  2. Check if both the stream has same number of elements, if not -> return false
  3. Check if root is same, if not -> return false
  4. leftsubtree arrays = constructed from smaller elements than root
  5. rightsubtree arrays = constructed from greater elements than root
  6. if leftsubtree == rightsubtree -> return true
  7. For finding result in step 6, follow above steps recursively

Code: While writing code, I am skipping the element equal to root.

Ruby:
def checkidenticaltree(a, b)
return false if a.length != b.length
return false if a[0] != b[0]
return true if a.length <= 1

a_left = a.select {|v| v < a[0]}
a_right = a.select {|v| v > a[0]}
b_left = b.select {|v| v < b[0]}
b_right = b.select {|v| v > b[0]}

return checkidenticaltree(a_right, b_right) && checkidenticaltree(a_left, b_left)
end

Python:
def checkidenticaltree(a, b):
if len(a) != len(b):
return False
if a[0] != b[0]:
return False
if len(a) <= 1:
return True

a_left = []
a_right = []
for x in a:
if x < a[0]:
a_left.append(x)
elif x > a[0]:
a_right.append(x)

b_left = []
b_right = []
for x in b:
if x < b[0]:
b_left.append(x)
elif x > b[0]:
b_right.append(x)

return checkidenticaltree(a_right, b_right) and checkidenticaltree(a_left, b_left)


PS: This is not a very efficient approach as we have to segment stream on each recursion. It will be great, if we can find some bottom-up approach. Any suggestions?

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.