Lowest Common Ancestor of a Binary Tree

1. Define the problem

Lowest Common Ancestor of a Binary Tree

Given a binary tree and two values p and q that both appear in it, return the value of their lowest common ancestor : the deepest node that has both of them somewhere below it. A node counts as being below itself, so if p sits above q then p is the answer. The tree arrives as a level-order array such as [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], with null for a missing child. p and q arrive as plain numbers, and your function returns a plain number. Ask every node one question: did I find p or q below me? If a node hears yes from both of its sides, that node is the meeting point. If it hears yes from only one side, it passes that answer upwards.

Constraints

The number of nodes is between 2 and 10⁵
All node values are unique
p and q are different values and both exist in the tree, unless the tree has a single node
Input is a level-order array with null for a missing child

Example

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

Output3

Explanation 5 sits in the left half of the tree and 1 sits in the right half. The only node with both of them below it is the root 3, so the answer is 3.

2. Know the words first

In plain terms

Ancestor: Any node you pass through on the way down from the root to a given node, including the node itself.
Lowest common ancestor: Of the nodes that have both p and q below them, the one furthest from the root. There is always exactly one.
Bubbling up: Letting each recursive call hand its answer back to the call above it, so a discovery deep in the tree travels up to the top.

3. Visualize the solution

Level-order slots; the label is the node value and the cell shows what that node reports upwards

3—

5—

1—

6—

2—

0—

8—

Statusinit

The search starts at the root 3, looking for 5 and 1.

What happens in this step

values = [3, 5, 1, 6, 2, 0, 8, ...], p = 5, q = 1

Slot 0 is the root 3.
Its children are 5 (left) and 1 (right).

Nothing has been reported yet.

Step 1 of 5

Steps to visualize

Each cell is one slot of the tree read level by level; the label is the value stored there.
A node reports back either nothing, or the node where p or q was found.
A node that is itself p or q reports itself straight away and never looks below.
The first node that hears a report from both sides is the answer.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Level-order slots; the label is the node value and the cell shows what that node reports upwards

3—

5—

1—

6—

2—

0—

8—

Statusinit

The search starts at the root 3, looking for 5 and 1.

What happens in this step

values = [3, 5, 1, 6, 2, 0, 8, ...], p = 5, q = 1

Slot 0 is the root 3.
Its children are 5 (left) and 1 (right).

Nothing has been reported yet.

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

function lowestCommonAncestor(values, p, q) {
  function Node(value) {
    this.val = value;
    this.left = null;
    this.right = null;
  }

  function buildTree(list) {
    if (list.length === 0 || list[0] === null) {
      return null;
    }

    const root = new Node(list[0]);
    const queue = [root];
    let i = 1;

    while (i < list.length && queue.length > 0) {
      const node = queue.shift();

      if (list[i] !== null && list[i] !== undefined) {
        node.left = new Node(list[i]);
        queue.push(node.left);
      }

      i += 1;

      if (list[i] !== null && list[i] !== undefined) {
        node.right = new Node(list[i]);
        queue.push(node.right);
      }

      i += 1;
    }

    return root;
  }

  function lca(node) {
    if (node === null) {
      return null;
    }

    if (node.val === p || node.val === q) {
      return node;
    }

    const left = lca(node.left);
    const right = lca(node.right);

    if (left !== null && right !== null) {
      return node;
    }

    return left !== null ? left : right;
  }

  const found = lca(buildTree(values));

  return found === null ? -1 : found.val;
}

Time: O(n)
Space: O(h)

6. Test cases

Test cases

Input	Expected	Covers
`values = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 1`	`3`	example from the docstring
`values = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 4`	`5`	one target sits above the other
`values = [1, 2], p = 1, q = 2`	`1`	smallest tree, the root is one of the targets
`values = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 7, q = 4`	`2`	the meeting point is deep inside the tree, not the root
`values = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 6, q = 8`	`3`	targets in opposite corners meet at the root
`values = [1], p = 1, q = 1`	`1`	a single node that is both targets

Lowest Common Ancestor of a Binary Tree