Lowest Common Ancestor

Given a binary tree and two nodes **p** and **q**, find their **Lowest Common Ancestor (LCA)**.

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

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

Output: 3

LCA of 5 and 1 is 3.

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

Output: 5

LCA of 5 and 4 is 5, since 5 is an ancestor of 4.

Time

O(n)

potentially visit all nodes.

Space

O(h)

recursion stack.

#1 LCA is root

Input: [3,5,1,6,2,0,8,null,null,7,4] p=5 q=1

Expected: 3

#2 One is ancestor of other

Input: [3,5,1,6,2,0,8,null,null,7,4] p=5 q=4

Expected: 5

#3 Root and child

Input: [1,2] p=1 q=2

Expected: 1