PROGRAMMING INTERVIEWS

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?