Solution: Lowest Common Ancestor of a Binary Tree III

Explore how to determine the lowest common ancestor of two nodes in a binary tree when nodes have parent pointers. Learn a two-pointer approach that moves each pointer up the tree and switches starting nodes to equalize travel distance, ensuring the meeting point is the lowest common ancestor. This lesson helps you understand time and space efficient tree traversal without needing the root node.

We'll cover the following...

Statement
Solution
- Time complexity
- Space complexity

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