Recursion

Lowest Common Ancestor

Given the root node of a binary tree root and two values in the tree p and q, return the value of their lowest common ancestor. All the values in the tree are unique.

Example:

\notag \begin{align*} &\large \texttt{p = 6} \\ &\large \texttt{q = 15} \\[8bp] &\large \texttt{=> returns 3} \end{align*}

First Few Test Cases:

lowestCommonAncestorValue(TreeNode.of([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]), 6, 15)
# 3

lowestCommonAncestorValue(TreeNode.of([1, 2, 3]), 1, 2)
# 1

lowestCommonAncestorValue(TreeNode.of([1, 2, 3]), 2, 3)
# 1

0. Problem

The LCA is the node where p is to the left and q is to the right, or vice versa:

The LCA can also equal p and have q in one of its subtrees, or vice versa:

Putting these together, here's the equation for the LCA. The function hasPorQ computes whether p or q shows up in a subtree.

LCA = ( # LCA = the highest node where this holds

    # p and q are both children
    (hasPorQ(node.left) and hasPorQ(node.right))
    
    # equal to p or q
    or node.val == p or node.val == q 

)

1. Recursion

It's not obvious how to find a recursion for LCA, but we definitely need to compute hasPorQ at each node in the tree, so we might as well find a recursion for that. Here's the recursion for hasPorQ:

hasPorQ(node) = (
    node.val == p or node.val == q
    or hasPorQ(node.left)
    or hasPorQ(node.right)
)

Notice that this recursion already computes everything we need in order to compute the LCA. So a clever idea is to "hijack" it, and use it to compute the LCA. We can do this by just copying the above recursion and sticking in a line of code:

hasPorQ(node) =  (
    leftHas = hasPorQ(node.left)
    rightHas = hasPorQ(node.right)
    nodeEquals = (node.val == p or node.val == q)

    # stick in a line of code to compute LCA
    # ---------------------------------------- #
    if (leftHas and rightHas) or nodeEquals: # from step 0
        LCA = node
    # ---------------------------------------- #
    
    return nodeEquals or leftHas or rightHas
)

2. Base case

The base case is:

hasPorQ(null) = False

3. Code

We just have to combine the recursion and base case. We'll keep a global variable "LCA", and update it when we see a node that could be the LCA. Here's the code:

def lowestCommonAncestorValue(root, p, q):
    LCA = None

    def hasPorQ(node):
        # base case
        if node is None:
            return False
        
        # recursion
        leftHas = hasPorQ(node.left)
        rightHas = hasPorQ(node.right)
        nodeEquals = (node.val == p or node.val == q)

        # stick in a line of code to compute LCA
        # ------------------------------------------ #
        if nodeEquals or (leftHas and rightHas):
            nonlocal LCA
            LCA = node
        # ------------------------------------------ #
        
        return nodeEquals or leftHas or rightHas

    hasPorQ(root) # run hijacked function and return result
    return LCA.val

Note that hasPorQ runs on low nodes first and high nodes last, because it gets set after hasPorQ was already called on the node's children. This is important, because we need to return the highest node that satisfies this equation.

Time Complexity $O(n)$ . We visit each node once and do an $O(1)$ operation on it.

Space Complexity $O(n)$ . The Call Stack grows up to size $n$ .

Mark as Completed:

Submits:

lowestCommonAncestorValue

Imports:

TreeNode

Test your code to get an output here!

lowestCommonAncestorValue(

)

Test your code to get an output here!