636. Lowest Common Ancestor of a Binary Tree III
This variant of lowest common ancestor hands you the two nodes but not the root. Every node of the binary tree carries three links — left, right, and parent — and all values in the tree are unique.
Given references to two distinct nodes p and q in the same tree, return the lowest common ancestor: the deepest node whose subtree contains both p and q. A node counts as its own ancestor, so if p sits somewhere above q, the answer is p itself.
The parent pointers change everything: you never search downward. Following parent from any node traces a chain up to the root, so p and q each define an upward path — and you are really being asked for the first node where those two paths merge.
Your function receives the two Node objects and returns the LCA Node (the judge prints its value).
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: the node with value 3
Explanation: Node 5 and node 1 sit in different subtrees of the root; their upward parent chains first meet at node 3.
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: the node with value 5
Explanation: Node 4 lives inside node 5's subtree (4 → 2 → 5), so node 5 is an ancestor of node 4 — and a node counts as its own ancestor.
Constraints:
- 2 ≤ number of nodes ≤ 10⁵
- -10⁹ ≤ Node.val ≤ 10⁹, all values unique
- p ≠ q, and both p and q exist in the tree
Hints:
Forget it's a tree. Each node's parent chain is a linked list ending at the root, so p and q give you two upward lists that share their tail. You need the first shared node.
Walk from p to the root, storing every node you visit in a hash set (include p itself). Then walk up from q: the first node already in the set is the LCA. O(h) time, O(h) extra space.
O(1) space: two pointers, one starting at p and one at q. Step each upward; when a pointer runs off the root, restart it at the OTHER start node. Both pointers travel depth(p) + depth(q) steps, so they land on the first shared node at the same moment — the same trick as Intersection of Two Linked Lists.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Expected output: 3