Lowest Common Ancestor of a Binary Tree III

Explore how to determine the lowest common ancestor (LCA) of two nodes in a binary tree when only parent pointers are provided. This lesson helps you apply logic to traverse upward from nodes p and q, understanding the concept of descendants and leveraging the two pointers technique in trees. You will learn to implement an efficient solution without access to the root, preparing you for coding interviews focused on tree traversal and ancestor queries.

We'll cover the following...

Statement
Example
Understand the problem
Figure it out!
Try it yourself

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: