**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:

- Make first element as root.
- If current element is smaller then root -> insert in left subtree.
- If current element is greater then root -> insert in right subtree.
- If current element is equal to root -> skip (or as pre-decided)
- 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:

- Check if stream is finished if yes -> return false
- Check if both the stream has same number of elements, if not -> return false
- Check if root is same, if not -> return false
- leftsubtree arrays = constructed from smaller elements than root
- rightsubtree arrays = constructed from greater elements than root
- if leftsubtree == rightsubtree -> return true
- 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.
Anonymousyou can go for level order traversal to check if correspondind nodes are equal