SIMILAR/SAME/EQUAL BST

 An array of integer makes a bst obtained by inserting values from left to right in bst.

Write a function that takes 2 arrays and determines whether they are same bst or not. 

NOTE : CONSTRUCTING BST IS NOT ALLOWED.

SAMPLE TEST CASE 1: 

arrayOne : [10, 15, 8, 12, 94, 81, 5, 2, 11]

arrayTwo : [10, 8, 5, 15, 2, 12, 11, 94, 81]

SAMPLE OUTPUT :  true 

        Approach :  

We know that we have to traverse array from left to right, so its obvious that element at 0th index will be the root of the tree.

So we will break the problem into smaller problem first we will check if 0th element of both the array is same then it can be same tree.

Now we will break array 1 into two array i.e. leftOne(array that will make left sub tree), rightOne(array that will make right sub tree.

For arrayOne : leftOne = [ 8, 5, 2] , rightOne = [15, 12, 94, 81, 11]

        

getSmaller returns leftOne and getBiggerOrEqual returns rightOne.

        Conditions for not same tree :

1. if length of both arrays is not equal.

2. if the first element of both trees is not equal.

      Time - O(n*n)

       Space - O(n*n)

Solution - same tree solution

 

 Please leave comment for any suggestions or topic you would like to read.