Solution: Lowest Common Ancestor in a Binary Tree

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 and q, is defined as the lowest node in the binary tree that has both p and q as descendants.

A node can also be a descendant of itself. For example, if q is a descendant of p, and we know that p is a descendant of itself, then p will be the lowest common ancestor of p and q.

Constraints:

• $2 \leq n \leq 500$
• All Node.data are unique.
• p $!=$ q
• p and q exist in the tree.

Solution

We will use depth-first search to find the lowest common ancestor of p and q in the binary tree. The algorithm to find the lowest common ancestor of p and q is as follows:

1. First, we initialize three tracking variables, mid, left, and right, to track whether p or q has been found.

2. Then, we traverse the binary tree recursively using depth-first search starting from the root node.

3. If we find p or q during our traversal of the binary tree, we set the mid variable to TRUE and return mid.

4. The left tracking variable is used to store the result of the left subtree of the current node, and right 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.

5. Finally, during the traversal of the binary tree, if any two of the tracking variables, mid, left, or right, are TRUE, we set the current node as our answer node because this node will be the lowest common ancestor of p and q.

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: