Given the
root
node of a binary tree, write a program to find the
lowest common ancestor (LCA)
of two given nodes in the tree.
Problem Note
-
Lowest Common ancestor:
The lowest common ancestor is defined between two nodes
node1
andnode2
as the lowest node in a tree that has bothnode1
andnode2
as descendants (where we allow a node to be a descendant of itself). - All of the node's values will be unique.
-
node1
andnode2
are different and both values will exist in the binary tree. - You can use extra memory, helper functions, and can modify the node struct but, you can’t add a parent pointer.
Given the following binary tree:
root
= [5, 6, 3, 1, 7, 9, 4, null, null, 2, 0]
Example 1
Input: root = [5, 6, 3, 1, 7, 9, 4, null, null, 2, 0]
node1 = 6, node2 = 3
Output: 5
Explanation: The LCA of nodes 6 and 3 is 5.
Example 2
Input: root = [5, 6, 3, 1, 7, 9, 4, null, null, 2, 0]
node1 = 6, node2 = 0
Output: 6
Explanation: The LCA of nodes 6 and 0 is 6, since a node can be a descendant of itself according to the LCA definition.