Identical BSTs

Easy
0/40
Average time to solve is 10m
profile
Contributed by
8 upvotes
Asked in company
Samsung

Problem statement

Given two arrays, ‘ARR1’ and ‘ARR2’ each of size ‘N’, representing a sequence of keys. Find out whether the two Binary Search Trees (generated from the arrays) will be identical or not without actually constructing the tree. Return ‘True’ if the BSTs are identical. Otherwise, return ‘False’.

Binary Search Tree (BST) properties:

  • The left subtree of a node contains values strictly lesser than the node’s value.
  • The right subtree of a node contains values strictly greater than the node’s value.
  • The left and right subtree of each node must be a BST.
  • There should not be any duplicate nodes.

Constructing BST from the given array:

  • The ‘0-th’ element is always the root node of the BST.
  • After that, traverse the array elements in the given sequence and insert/add them to the BST. The new nodes must be inserted at one of the leaf nodes (as its child), while maintaining the BST property.

Example : 
‘N’ = 4, ‘ARR1’ = [2, 4, 1, 3] and ‘ARR2’ = [2, 4, 3, 1]

The following diagram shows how to construct a BST from the input array (you have to solve this problem without actually constructing the tree)

BST for ‘ARR1’ = [2, 4, 1, 3]:

input1

BST for ‘ARR2’ = [2, 4, 3, 1]:

input2

As the BSTs constructed from ‘ARR1’ and ‘ARR2’ are identical, you should return ‘True’ as the answer.
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first line of input contains a single integer ‘N’ denoting the size of the arrays ‘ARR1’ and ‘ARR2’.

The second line of each test case contains ‘N’ space-separated integers representing the array ‘ARR1’.

The third line of each test case contains ‘N’ space-separated integers representing the array ‘ARR2’.
Output Format: 
For each test case, print ‘True’ if the BSTs constructed from ‘ARR1’ and ‘ARR2’ are identical. Otherwise, return ‘False’.

The output of each test case will be printed in a separate line.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 10
1 <= N <= 3*10^3

The values in the arrays ‘ARR1’ and ‘ARR2’ range from ‘[1, 10^9]’.

Time Limit: 1 sec
Sample Input 1:
2
5
4 3 5 6 2
4 5 6 3 2
4
5 7 6 4
5 4 6 7
Sample Output 1:
True
False
Explanation For Sample Input 1:
For the first test case :

BST for ‘ARR1’ = [4, 3, 5, 6, 2]:

sample11

BST for ‘ARR2’ = [4, 5, 6, 3, 2]

sample12

As the BSTs constructed from ‘ARR1’ and ‘ARR2’ are identical, you should return ‘True’ as the answer.

For the second test case :

BST for ‘ARR1’ = [5, 7, 6, 4]:

sample21

BST for ‘ARR2’ = [5, 4, 6, 7]:

sampe22

As the BSTs constructed from ‘ARR1’ and ‘ARR2’ are different, you should return ‘False’ as the answer.
Sample Input 2:
2
3
1 2 3
1 2 3
4
1 2 3 4 
5 6 7 8
Sample Output 2:
True
False
Hint

Try using recursion to check if the root node’s left and right child nodes are the same for both the arrays (or BSTs).

Approaches (1)
Recursive Approach

We know that the ‘0-th’ index of the given array is the root of the BST constructed from it.

 

Observation: The first value after the root node that has a smaller value than the root node will be the left child of the root node. Similarly, the first value larger than the root node will be the right child of the root node.

 

Apart from these two conditions, we need to check that the left child is greater than the parent of the root node (and smaller than the root node). The right child should be smaller than the parent of the root node (and greater than the root node).

 

To achieve this, we can recursively call for the left and right subtrees while maintaining two variables, ‘MIN’ and ‘MAX’, in the recursive function. The values ‘MIN + 1’ and ‘MAX - 1’ denote the minimum and maximum allowed values for the current root node. These values depend on whether the current root node is the left or right child of its parent node.
 

For the left child, ‘MIN = The value of the parent of root node’ and ‘MAX = the value of root node’.

For the right child, ‘MIN = The value of root node’ and ‘MAX = The value of the parent of root node’.

 

In the recursive function, check that the root node should be the same in both the arrays (or BSTs). Otherwise, return ‘False’. We break the recursion if the root node’s index in both the arrays is equal to ‘N’, i.e., when the root node’s parent is a leaf node in both the BSTs.

 

ALGORITHM:

  • Return ‘isIdenticalBSTUtil(ARR1, ARR2, N, 0, 0, INT32_MIN, INT32_MAX)’. This is a helper function used to handle the recursion. Initially, ‘MIN = INT32_MIN’ and ‘MAX = INT32_MAX’ to make sure that the ‘0-th’ index is always selected as the root node for the first function call.
     

For the following function, ‘i1’ and ‘i2’ are the indexes from which we need to search for the root node for ‘ARR1’ and ‘ARR2’, respectively.

 

‘Boolean isIdenticalBSTUtil(array ARR1, array ARR2, integer N, integer i1, integer i2, integer MIN, integer MAX)’:

  • Initialize two integers, ‘ROOT1’ and ‘ROOT2’. Use them to find the index of the current root node for the respective arrays.
  • Run a loop where ‘ROOT1’ ranges from ‘i1’ to ‘N - 1’:
    • If ‘ARR1[ROOT1] > MIN’ and ‘ARR1[ROOT1] < MAX’, then we have found the first value satisfying the condition for the root node of ‘ARR1’:
      • Break the loop.
  • Run a loop where ‘ROOT2’ ranges from ‘i2’ to ‘N - 1’:
    • If ‘ARR2[ROOT2] > MIN’ and ‘ARR2[ROOT2] < MAX’, then we have found the first value satisfying the condition for the root node of ‘ARR2’:
      • Break the loop.
  • If ‘ROOT1 == N’ and ‘ROOT2 == N’, then the parent of the current root node is a leaf node in both the BSTs, so we need to end the recursion:
    • Return ‘True’, as all the previous nodes are the same in both the BSTs.
  • If ‘(ROOT1 == N) ^ (ROOT2 == N)’, then one of the current root nodes has a leaf node as its parent node and the other one doesn’t, so the two BSTs aren’t identical:
    • Return ‘False’. (‘^’ is the XOR operator)
  • If ‘ARR1[ROOT1] != ARR2[ROOT2]’, then the current root nodes of the two BSTs aren’t equal, then the two BSTs cannot be identical:
    • Return ‘False’.
  • Set ‘LEFT = isIdenticalBSTUtil(ARR1, ARR2, N, ROOT1 + 1, ROOT2 + 1, MIN, ARR1[ROOT1])’. Check if the left subtree of two the BSTs are identical.
  • Set ‘RIGHT = isIdenticalBSTUtil(ARR1, ARR2, N, ROOT1 + 1, ROOT2 + 1, ARR1[ROOT1], MAX)’. Check if the right subtree of two the BSTs are identical.
  • Return ‘LEFT && RIGHT’. Check if both ‘LEFT’ and ‘RIGHT’ are equal to ‘True’. (‘&&’ is the AND operator)
Time Complexity

O(N^2), where ‘N’ is the size of the arrays ‘ARR1’ and ‘ARR2’.

 

If the constructed BST is a skewed tree, then in each recursion, the root node will be at index ‘i1’ or ‘i2’, and we will have to traverse the entire array from ‘i1’ or ‘i2’ to ‘N - 1’ (as one of the children doesn’t exist), taking ‘O(N^2)’ time. Thus, the time complexity is ‘O(N^2)’.

Space Complexity

O(N), where ‘N’ is the size of the arrays ‘ARR1’ and ‘ARR2’.

 

The size of the recursion stack used is equal to the height of the BST. For a skewed tree, the height will be ‘N’. Thus, we need ‘O(N)’ space.

Code Solution
(100% EXP penalty)
Identical BSTs
Full screen
Console