Solution: Lowest Common Ancestor of a Binary Tree
Let's solve the Lowest Common Ancestor of a Binary Tree problem using the Tree DepthFirst Search pattern.
We'll cover the following
Statement
Given the root node of a binary tree with $n$ nodes, your task is to find the lowest common ancestor of two of its nodes, p
and q
.
Note: The lowest common ancestor of two nodes,
p
andq
, is defined as the lowest node in the binary tree that has bothp
andq
as descendants.A node can also be a descendant of itself. For example, if
q
is a descendant ofp
, and we know thatp
is a descendant of itself, thenp
will be the lowest common ancestor ofp
andq
.
Constraints:
 $2 \leq n \leq 500$
 All
Node.data
are unique. p
$!=$q
p
andq
exist in the tree.
Solution
Start from the root and recursively search the left and right subtrees. At each node, check if it matches either of the two given nodes. If it does, return that node since itâ€™s a potential ancestor. Otherwise, continue searching for the nodes in both subtrees. As the recursion explores the left and right subtrees, it returns a node if one of the given nodes is found or returns null if neither node is found in that subtree.
At each node, if only one of the subtrees returns a nonnull result, it means both nodes are located in that subtree. The nonnull result propagates upwards as you search for the lowest common ancestor.
If both the left and right recursive calls return a nonnull result, one node was found in the left subtree and the other in the right subtree. In this case, the current node is the lowest common ancestor, so return the current node as the result.
The implementation details of the above algorithm to find the lowest common ancestor of p
and q
are as follows:

First, we initialize three tracking variables,
mid
,left
, andright
, to track whetherp
orq
has been found. 
Then, we traverse the binary tree recursively using depthfirst search starting from the
root
node. 
If we find
p
orq
during our traversal of the binary tree, we set themid
variable to TRUE and returnmid
. 
The
left
tracking variable is used to store the result of the left subtree of the current node, andright
tracking variable is used to store the result of the right subtree of the current node. So, the results from the recursive calls are stored in their respective tracking variables. 
Finally, during the traversal of the binary tree, if any two of the tracking variables,
mid
,left
, orright
, are TRUE, we set the current node as our answer node because this node will be the lowest common ancestor ofp
andq
.
We need to understand the purpose of each of the tracking variables to answer the question of how a node becomes the lowest common ancestor if any two of the tracking variables are TRUE. If the left
and right
variables are TRUE for any node, it means that both the nodes are descendants of the current node, and therefore, the current node is the lowest common ancestor of the two nodes. However, if mid
and either one of the left
or right
variables are TRUE, then either p
or q
is the current node itself, and the other is the descendant of the current node. Since a node is an ancestor of itself, the lowest common ancestor of the input nodes is the current node.
Letâ€™s look at the following illustration to get a better understanding of the solution:
Level up your interview prep. Join Educative to access 80+ handson prep courses.