Print Common Elements

Easy
0/40
Average time to solve is 15m
profile
Contributed by
6 upvotes
Asked in companies
TwitterOla

Problem statement

Given two Binary Search Trees, your task is to return a list of integers which contains the values that are present in both the Binary Search Trees.

For example: 
If the binary search trees look like the ones below:


The only common values are 6 and 7, therefore we return the list [6, 7].
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases are as follows.

The first line of each test case contains elements of the first tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.

The second line of each test case contains elements of the second tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.
For example: 
The input for the tree depicted in the below image would be :

Example

Input Format:   
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, return a list containing the common elements.

Output for each test case will be printed in a new line.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the given functions.
Constraints: 
1 <= T <= 100
1 <= N <= 10 ^ 5
-10 ^ 9 <= val <= 10 ^ 9

where “val” represents the values stored in the nodes

Time Limit: 1sec
Sample Input 1:
2
7 6 -1 -1 -1 
4 -1 7 6 8 -1 -1 -1 -1
5 -1 8 -1 9 -1 -1 
7 1 9 -1 -1 8 10 -1 -1 -1 -1
Sample Output 1:
6 7
8 9

Explanation For Sample Output 1:

In the first case,
The first and second Binary Search Trees looks like:


Clearly, the only common elements are 6 and 7. Therefore we return the list [6, 7].

In the second case,


Both the trees have common elements 8 and 9, therefore we return the list [8, 9].
Sample Input 2:
2
8 5 10 2 6 -1 -1 -1 -1 -1 7 -1 -1
10 5 12 1 6 -1 -1 -1 -1 -1 -1
8 5 10 2 6 -1 -1 -1 -1 -1 7 -1 -1
2 -1 6 -1 8 -1 -1
Sample Output 2:
5 6 10
2 6 8
Hint

For each element in the first Binary Search Tree can we check if it exists in the second one?

Approaches (2)
Brute Force

For each element in the first Binary Search Tree, we can check if it exists in the second tree. Since it is a Binary Search Tree, we can perform the search operation in log(N) time, where ‘N’ is the number of nodes in the Binary Search Tree.
 

Algorithm:

 

  • Initialize two pointers “ptr1” and “ptr2” which initially point towards the root of both the Binary Search Trees.
  • Initialize the result list “commonValues” which is empty initially.
  • Use “ptr1” to iterate through the first Binary Search Tree and for each node:
    • If value at “ptr1” is less than “ptr2”:
      • Update “ptr2” to be the left child of “ptr2”
    • If value at “ptr1” is greater than “ptr2”:
      • Update “ptr2” to be the right child of “ptr2”
    • If “ptr2” is NULL, we have not found the value that “ptr1” points to in the second Binary Search Tree. At this point continue iterating through the first Binary Search Tree using “ptr1”.
    • If the values that “ptr1” and “ptr2” point to are equal, insert the value into “commonValues”.
  • Return “commonValues”.
Time Complexity

O(N * log(M)), where ‘N’ denotes the number of nodes in the first tree and ‘M’ denotes the number of nodes in the second tree.

 

Note that for each node in the first Binary Search Tree, we search the element in the second Binary Search Tree which costs log(M) operations. Hence a time complexity of O(N * log(M)).

Space Complexity

O(min(N, M)), where ‘N’ denotes the number of nodes in the first tree and ‘M’ denotes the number of nodes in the second tree.
 

The resulting list has at most all elements of the smaller tree, hence a complexity of O(min(N, M)).

Code Solution
(100% EXP penalty)
Print Common Elements
Full screen
Console