Lowest Common Ancestor of Binary Tree

Lowest Common Ancestor of Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

The lowest common ancestor is defined as the lowest node in the tree that has both p and q as descendants (where we allow a node to be a descendant of itself).

Examples

Example 1:

Input: root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

          3
         / \
        5   1
       / \ / \
      6  2 0  8
        / \
       7   4

Example 2:

Input: root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself.

Constraints

• The number of nodes in the tree is in the range [2, 10^5].
• -10^9 <= Node.val <= 10^9
• All Node.val are unique.
• p != q
• p and q exist in the tree.

Expected Complexity

• Time: O(n)
• Space: O(h) where h is the height of the tree