Same BST

Moderate
0/80
Average time to solve is 15m
2 upvotes
Asked in company
Codenation

Problem statement

You are given two binary search trees. Your task is to check whether the two BSTs contains the same set of elements or not.

The structure of the two given BSTs can be different.

Note: All elements in a given BST are unique.

For Example:

alttext

The above two BSTs contain the same set of elements, hence the answer is True.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer ‘T’ denoting the number of test cases to be run. 
Then the test cases follow.

The first line of each test case contains the elements of the first binary tree in the level order form separated by a single space.

The Second line of each test case contains the elements of the second binary tree in the level order form separated by a single space.

If any node does not have a left or right child, take -1 in its place. Refer to the example below.


1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation :
Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.

The input ends when all nodes at the last level are null (-1).

Note: The above format was just to provide clarity on how the input is formed for a given tree. 
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
Output Format : 
For each test case, You have to return ‘true’ if BSTs contain the same set of elements or ‘false’ if BSTs don’t contain the same set of elements.

Output for each test case will be printed in a separate line.
Note: 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 100 
1 <= N <= 1000

Time Limit: 1 sec
Sample Input 1:
2
8 5 10 2 6 -1 -1 -1 -1 -1 7 -1 -1
10 5 -1 -1 2 8 -1 -1 6 -1 -1 
26 -1 52 -1 78 -1 -1 
26 -1 52 -1 78 -1 -1
Sample Output 1:
false
true
Explanation For Sample Output 1:
In test case 1:
The  first binary tree will be like the following:


The elements in the first tree are 8, 5, 10, 2, 6, 7.

The second tree will be like the following:


The element in the second tree are 10, 5, 2, 8, 6

Here the elements are not the same in both the trees, hence the output will be “false”.

Test Case 2:

In the second case both trees are identical, and look like this:


Hence the output will be “true”.
Sample Input 2:
2
40 20 60 -1 -1 -1 80 -1 -1 
40 20 60 -1 -1 -1 80 -1 -1 
9 5 12 2 6 10 15 -1 -1 -1 -1 -1 -1 -1 -1
12 9 15 5 10 -1 -1 2  -1 -1 -1 -1 -1
Sample Output 2:
true
false
Hint

Inorder traversal of Binary Search tree gives nodes in non-decreasing order.

Approaches (1)
Inorder Traversal.

Traverse both the tree in an Inorder fashion, store the value in hashsets and check for values at every index.

 

Algorithm:-

 

  1. Store the Inorder traversal of the first tree in a hashSet (INORDER1).
  2. Store the Inorder traversal of the second tree in another HashSet (INORDER2).
  3. Check for the values in the HashSet at every index. If values don’t found in the other HashSet then return false otherwise true if all values are found.
  4. To Traverse on the tree in inorder fashion :
    1. Traverse the left subtree.
    2. Visit the node and store its value in the array.
    3. Traverse the right subtree.
Time Complexity

O(N), where N is the number of nodes in the tree.


We are traversing on both the tree once.Hence the overall time complexity will be O(N).

Space Complexity

O(N), where N is the number of nodes in the tree.
 

Two HashSet of size ‘n’ are used to store the values, hence the overall time complexity will be O(N).

Code Solution
(100% EXP penalty)
Same BST
Full screen
Console