New update is available. Click here to update.
sidenav-btnClose
Topic list
LCA of three Nodes
EASY
20 mins
4771 upvotes
Trees
Topics (Covered in this problem)
Problem solved
Skill meter
Trees
-
Other topics
Problem solved
Skill meter
Strings
-
Matrices (2D Arrays)
-
Sorting
-
Binary Search
-
Linked List
-
Stacks & Queues
-
Graph
-
Dynamic Programming
-
Greedy
-
Tries
-
Arrays
-
Binary Search Trees
-
Heap
-
Bit Manipulation
-

LCA of three Nodes

Contributed by
Ashwani
Easy
Avg time to solve 20 mins
Success Rate 60 %
Share
4771 upvotes

Problem Statement

You have been given a Binary Tree of 'N' nodes where the nodes have integer values and three integers 'N1', 'N2', and 'N3'. Find the LCA(Lowest Common Ancestor) of the three nodes represented by the given three('N1', 'N2', 'N3') integer values in the Binary Tree.

For example:

For the given binary tree: the LCA of (7,8,10) is 1
Note:
All of the node values of the binary tree will be unique.

N1, N2, and N3  will always exist in the binary tree.
Detailed explanation ( Input/output format, Notes, Constraints, Images )
Sample Input 1:
1
8 9 11
1 2 3 4 5 6 7 8 9 -1 -1 -1 -1 -1 -1 10 -1 11 -1 -1 -1 -1 -1
Sample Output 1:
4
Sample Input 2:
2
7 8 2
1 2 3 4 5 6 7 8 9 -1 -1 -1 -1 -1 -1 10 -1 11 -1 -1 -1 -1 -1
5 6 7
1 2 3 4 5 6 7 8 9 -1 -1 -1 -1 -1 -1 10 -1 11 -1 -1 -1 -1 -1
Sample Output 2:
1
1
Explanation to Sample Input 2:
For both inputs, the binary tree will be represented as

For the first test case, the LCA of 7,8,2 in the given tree is 2 

For the second test case. the LCA of 5,6,7 in the given tree is 1,   
Reset Code
Full screen
copy-code
Console