The deepest node both of them are under

Given a binary tree and two values p and q that both appear in it, report the value of their lowest common ancestor: the deepest node that has both of them somewhere beneath it.

A node counts as an ancestor of itself, so if one of them sits above the other, that one is the answer.

Worked example#

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

• p = 5, q = 1 gives 3, the root, because that is where the two branches part.
• p = 5, q = 4 gives 5, because 4 is beneath 5 and a node is its own ancestor.

The idea#

Every node in the tree is in exactly one of three situations:

1. It is p or q. Then it is the deepest thing worth reporting from this subtree, so report it upwards.
2. It found something on both sides. Then p came from one side and q from the other, so the paths part here and this node is the answer.
3. It found something on one side only. Then whatever it found is the best answer so far in this subtree, so pass it up unchanged.

Write that as a recursion and the algorithm is four lines:

walk(node):
    if node is nothing, or node is p, or node is q:
        return node
    left  = walk(node.left)
    right = walk(node.right)
    if both are non-empty:  return node      # the paths part here
    return whichever one is non-empty

The part worth pausing on#

Case 1 returns as soon as it sees p, without checking whether q is beneath it. That looks wrong and is not. If q is beneath p, then p is the answer, and returning p upward gives exactly that. If q is elsewhere, some node higher up will see p from one side and q from the other, and case 2 catches it.

This is one recursion, one pass, no parent pointers and no stored paths.

Constraints#

• 1 <= number of nodes <= 100000
• p and q both appear in the tree, and are different values

About the input#

The tree is written level by level with null for a missing child, the count first, then p, then q.