Last Updated: 6 Dec, 2020

Print Common Elements

Easy

Asked in companies

Solve now

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].

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

Solve now

Approaches

01 Approach

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”.

Solve now

02 Approach

We can solve the problem by keeping two pointers that traverse both the trees in inorder traversal separately.

In each step, if the values that both pointers are pointing to are the same, we append the node value into our result and increment both the pointers. If they point to different values, increment the pointer pointing to the lesser value.

Algorithm:

Initialize two pointers “ptr1” and “ptr2” which we would use to traverse the tree in an inorder fashion.
Initialize the result list “commonValues” which is empty initially.
If the values that “ptr1” and “ptr2” point to are equal:
- Insert the value into “commonValues”.
- Increment “ptr1”.
- Increment “ptr2”.
If the value at “ptr1” is less than “ptr2”:
- Increment “ptr1”
If the value at “ptr2” is less than “ptr1”:
- Increment “ptr2”
Continue the above steps until one of “ptr1” and “ptr2” has completed the entire traversal.
Return “commonValues”.

Solve now