Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in C++

Solution: Lowest Common Ancestor of a Binary Tree III

Understand how to identify the lowest common ancestor in a binary tree when given two nodes with parent pointers. Explore the two-pointer method that moves upward from each node and switches starting points to ensure equal traversal distances. This technique helps you solve the problem with constant space and time proportional to the tree height.

We'll cover the following...

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. ...