Lowest Common Ancestor

BINARY TREE
RECURSION

Problem

Given the root of a binary tree and two distinct nodes node1 and node2, find the lowest common ancestor (LCA).

The LCA is defined as the lowest node in the tree that has both node1 and node2 as descendants (where we allow a node to be a descendant of itself).

Examples

findLowestCommonAncestor([1,2,3], 2, 3) // returns 1 // Both 2 and 3 root themselves at 1 findLowestCommonAncestor([1,2,3,null,4,5,6,7], 3, 6) // returns 3 // 6 has 3 as ancestor // Since a node can be descendant of itself, the common root is 3
Loading...