Least Common Ancestor

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
24 upvotes
Asked in companies
FacebookVisaGoogle

Problem statement

You are given an arbitrary binary tree with N nodes, whose nodes have their values in the range of integers. You are given two nodes x, y from the tree. You have to print the least common ancestor of these nodes.

Least common ancestor of two nodes x, y in a tree or directed acyclic graph is the lowest node that has both nodes x, y as its descendants.

For example look at the tree below, the LCA of node 1 and 5 is 3.

Note :

You have to return the deepest node which has both x, y as its descendants.
There may be cases where one of u or v is not present in the tree. In those cases, the reference provided to u or v will be NULL.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains a single integer T, representing the number of test cases.

The first and only line of each test case contains the values of the nodes of the tree in the level order form ( -1 for NULL node) Refer to the example for further clarification.

Example: Consider the binary tree altImage

The input of the tree shown in the above image will look like: 
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).
Output Format : 
For each test case, print the LCA of the given nodes in a separate line.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 50
1 <= N <= 10^4
1 <= nodeVal <= 10^9

Time Limit: 1 sec
Sample Input 1 :
2
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
7 5
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
4 2
Sample Output 1 :
1
2
Explanation for Sample Output 1 :
For the first test case, as shown in the above figure, the root of the tree is the deepest node which contains both the nodes 7 and 5 as its descendants, hence 1 is the answer.
For the second test case, since 4 is one of the children of 2, so 2 is the answer.
Sample Input 2 :
2
1 2 -1 3 -1 -1 -1
3 1
9 -1 -1
9 9
Sample Output 2 :
1
9
Hint

Recursion

Approaches (2)
Recursive Approach
  • We know that the binary tree is a recursive structure, so we can use recursion to find the answer.
  • Let getLCA() be the recursive function which takes the root of the tree and the two nodes u and v as a parameter and returns LCA of the nodes.
  • If the current subtree contains both the nodes, then the function result is their LCA.
  • Now if the root is equal to u or v, then root is the answer.
  • Let ‘left’ store the result of LCA in the left subtree of the current node. If both the nodes are not present, then return NULL
  • Let ‘right’ store the result LCA  in the right subtree. If both the nodes are not present, then return NULL.
    • Now if both left and right are NULL then return NULL
    • If left != NULL and right != NULL, then return root.
    • If left = NULL, then return right else return left.
Time Complexity

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

Space Complexity

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

Code Solution
(100% EXP penalty)
Least Common Ancestor
Full screen
Console