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 parent pointers are given but the root is unknown. Learn to apply a two-pointer strategy that moves up the tree and converges at the common ancestor, understanding its implementation and time-space complexity.
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,
pandq, is the lowest node in the binary tree, with bothpandqas descendants.In a tree, a descendant of a node is any node reachable by following edges downward from that node, including the node itself. ...