DIY: Lowest Common Ancestor of a Binary Tree III
Solve the interview question "Lowest Common Ancestor of a Binary Tree III" in this lesson.
We'll cover the following
Problem statement
Suppose you are given two nodes of a binary tree node1
and node2
. Your task is to find the lowest common ancestor (LCA) of these two nodes in the tree.
Note: The lowest node that has both
node1
andnode2
as its descendants (where we allow a node to be a descendant of itself), is called the lowest common ancestor (LCA) of these two nodes.
For this problem, you can assume that the values of all the nodes are positive and unique and node1 != node2
. Moreover, each node will have a reference to its parent node. The definition of Node
can be viewed in the code widget below.
Note: The tree in the following test cases will be displayed in the form of an array representing the level-order traversal of the corresponding binary tree. For any missing nodes, there will be a
-1
in the array.
Input
The input will be two nodes of a binary tree, node1
and node2
. The following are examples of input to the function:
// Sample Input 1:
3
/ \
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
root = [3,5,1,6,2,0,8,-1,-1,7,4], node1 = 5, node2 = 1
// Sample Input 2:
1
/
2
root = [1,2], node1 = 1, node2 = 2
Output
The output will a node that is the lowest common ancestor (LCA) of node1
and node2
. The following are examples of the outputs:
// Sample Output 1:
3
// Sample Output 2:
1
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.