0. Problem

We want to find the LCA of the tree, given the values of the two nodes.

LCA(root, p, q)

1. Recursion

We want to somehow include a Binary Search in our algorithm so that it runs quickly.

Let's use an example:

How can we use a binary search to find the answer? If we did a binary search for p, we would start out at the root node and move left. And if we did a binary search for q, we would also move left.

The idea is to keep following the binary search on p and q, until we get to a node where the binary search for the two nodes disagrees. For example, in the above image, when you're at the LCA, the binary search for p tells you to move left, and the binary search for q tells you to move right, so they disagree with each other.

Here's the recursion for this:

def LCA(root, p, q):

    # find direction of p
    pDir = None
    if p < root.val: pDir = 'left'
    if p > root.val: pDir = 'right'

    # find direction of q
    qDir = None
    if q < root.val: qDir = 'left'
    if q > root.val: qDir = 'right'

    # if the directions agree, follow them
    if pDir == qDir == 'left': return LCA(root.left, p, q)
    if pDir == qDir == 'right': return LCA(root.right, p, q)

    # otherwise we're at the LCA
    # this happens if the directions disagree
    # it also happens if pDir or qDir is still None (if root.val == p or root.val == q) which is also correct
    return root.val

2. Base case

The recursion automatically stops when we hit the LCA, so there's not really a base case here.

3. Code

Since there's no base case, the code is just the recursion above. We'll write it again for clarity:

def LCA(root, p, q):

    # find direction of p
    pDir = None
    if p < root.val: pDir = 'left'
    if p > root.val: pDir = 'right'

    # find direction of q
    qDir = None
    if q < root.val: qDir = 'left'
    if q > root.val: qDir = 'right'

    # if the directions agree, follow them
    if pDir == qDir == 'left': return LCA(root.left, p, q)
    if pDir == qDir == 'right': return LCA(root.right, p, q)

    # otherwise we're at the LCA
    return root.val

Time Complexity $O(n)$. This is really the height of our tree, which is O(n) since we're not necessarily given balanced BSTs.

Space Complexity $O(n)$ for the Call Stack. Again, this is really the height of our tree.

This is very easy to make iterative - see below.

def LCA(root, p, q):

    while True:
        # find direction of p
        pDir = None
        if p < root.val: pDir = 'left'
        if p > root.val: pDir = 'right'

        # find direction of q
        qDir = None
        if q < root.val: qDir = 'left'
        if q > root.val: qDir = 'right'

        # if the directions agree, follow them
        if pDir == qDir == 'left':
            root = root.left
            continue
        if pDir == qDir == 'right':
            root = root.right
            continue

        # otherwise we're at the LCA
        return root.val