Given a binary tree, find the lowest common ancestor (LCA) of two given nodes p and q. The LCA is defined as the lowest node in the tree that has both p and q as descendants (a node can be a descendant of itself).
root = [3,5,1,6,2,0,8,null,null,7,4], p=5, q=13root = [3,5,1,6,2,0,8,null,null,7,4], p=5, q=45root==null → return null; root==p or root==q → return rootleft = lca(root.left, p, q)right = lca(root.right, p, q)left != null && right != null → return root (THIS is LCA!)Each call returns the "found" node if it found p or q (or their ancestor), or null if neither was found. At any node: if both left and right calls returned non-null, it means p is in one subtree and q is in the other — so this node is the LCA. If only one side is non-null, that side already contains both targets (one is an ancestor of the other), so we propagate that result upward.
You could store the path from the root to p and the path to q, and find where they split. That works, but it needs two extra lists and two searches. A single postorder search can report what it found to its parent.
Ask each subtree: did you find p or q? If the current node is null, p or q, return it straight away. Otherwise search the left and the right subtree. If both sides return something, then p and q are split across this node, so this node is the answer. If only one side returns something, pass that up.
When both sides report a find, the current node is the split point. A node can be its own ancestor, which is why returning p or q early is correct.
Run the animation above on your own input, or watch the 2:17 video explanation of Lowest Common Ancestor of a Binary Tree with a dry run and Java code.