Solution: Lowest Common Ancestor of a Binary Tree III

Statement

You are given two nodes, p and q. The task is to return their lowest common ancestor (LCA). Both nodes have a reference to their parent node. The tree’s root is not provided; you must use the parent pointers to find the nodes’ common ancestor.

Note: The lowest common ancestor of two nodes, p and q, is the lowest node in the binary tree, with both p and q as descendants.

In a tree, a descendant of a node is any node reachable by following edges downward from that node, including the node itself.

Constraints:

• $-10^4 \leq$Node.data $\leq 10^4$

• The number of nodes in the tree is in the range $[2, 500].$

• All Node.data are unique.

• p != q

• Both p and q are present in the tree.

Solution

This solution finds the lowest common ancestor (LCA) of two nodes in a binary tree using a smart two-pointer approach. We start by placing one pointer at node p and the other at node q. Both pointers move up the tree at each step by following their parent pointers. If a pointer reaches the root (i.e., its parent is None), it jumps to the other starting node. This process continues until the two pointers meet. The key idea is that by switching starting points after reaching the top, both pointers end up traveling the same total distance, even if p and q are at different depths. When they meet, that meeting point is their lowest common ancestor.

The steps of the algorithm are as follows:

1. Initialize two pointers: ptr1 starting at p and ptr2 starting at q.

2. While ptr1 and ptr2 are not pointing to the same node:

   1. If ptr1 has a parent, move ptr1 to ptr1.parent; otherwise, set ptr1 = q.

   2. If ptr2 has a parent, move ptr2 to ptr2.parent; otherwise, set ptr2 = p.

3. When ptr1 == ptr2, return ptr1. This node is the lowest common ancestor (LCA) of p and q.

Let’s look at the following illustration to get a better understanding of the solution: