Lowest Common Ancestor of a Binary Tree

Medium~25 min

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 deepest node that is an ancestor of both p and q (a node can be an ancestor of itself).

The tree is given as a level-order array where null represents missing nodes, followed by the values of nodes p and q.

For example, given tree [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 1:

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

The LCA of nodes 5 and 1 is 3.

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, since 3 is the deepest node that has both 5 and 1 as descendants.
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 an ancestor of itself. Node 4 is in the subtree of 5.
Example 3
Input: root = [1,2], p = 1, q = 2
Output: 1
Explanation: The LCA of nodes 1 and 2 is 1 (the root is ancestor of all nodes).

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 will exist in the tree
  • Expected time complexity: O(n)
Code
Ctrl+EnterRun|Ctrl+⇧+EnterSubmit
Output

Run your code to see results

Use Cmd+Enter to run