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)

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?