LeetCode 1644 - Lowest Common Ancestor of a Binary Tree II

This problem asks us to find the lowest common ancestor (LCA) of two given nodes, p and q, in a binary tree, under the c

leetcodemediumtreedepth-first-searchbinary-tree

LeetCode Problem 1644

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

This problem asks us to find the lowest common ancestor (LCA) of two given nodes, p and q, in a binary tree, under the condition that either node might not exist in the tree. In other words, given a binary tree with unique values and two target nodes, we must determine the deepest node that is an ancestor to both p and q. If either p or q does not exist in the tree, we return null.

The input consists of the root node of a binary tree, and two nodes p and q. Each node in the tree has a unique integer value. The expected output is a reference to the TreeNode that is the LCA, or null if either node is missing.

The problem guarantees that p != q and that the number of nodes in the tree can be up to 10^4. This indicates that an O(n) traversal is acceptable but repeated traversals should be avoided for efficiency.

Important edge cases include:

  1. One of the nodes does not exist in the tree. A naive LCA algorithm would incorrectly return a node.
  2. The LCA is one of the nodes themselves. According to the definition, a node can be a descendant of itself.
  3. The tree is skewed (all nodes on one side), which tests the recursion depth and correctness.

Approaches

The brute-force approach involves first checking whether both nodes exist in the tree using separate traversals. After confirming existence, one could use the standard LCA algorithm that recursively searches for p and q in the left and right subtrees. While correct, this requires multiple traversals of the tree, making it inefficient for large trees.

The optimal approach combines the existence check and the LCA search into a single recursive traversal. We define a recursive function that returns both whether p or q exists in a subtree and the LCA if it exists. At each node, we recursively check left and right children, then determine if the current node is the LCA. This ensures that we traverse the tree only once and correctly handle the case where a node is missing.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Two traversals: one for existence check, one for LCA
Optimal O(n) O(h) Single DFS, where h is tree height; returns LCA only if both nodes exist

Algorithm Walkthrough

  1. Define a recursive function dfs(node) that traverses the tree. For each node, it will return a tuple (found_p, found_q, lca).
  2. If the current node is None, return (False, False, None) since neither target exists in an empty subtree.
  3. Recursively traverse the left child and right child, obtaining (left_p, left_q, left_lca) and (right_p, right_q, right_lca).
  4. Determine if p and q exist in the current subtree: found_p = left_p or right_p or node == p, found_q = left_q or right_q or node == q.
  5. Determine the LCA:
  • If left_lca is not None, propagate it upward.
  • If right_lca is not None, propagate it upward.
  • If p and q are found in different subtrees (one in left, one in right) or the current node is p or q and the other node exists in a child, then the current node is the LCA.
  1. Return (found_p, found_q, lca) for the current node.
  2. At the root, check if both p and q are found. If yes, return the lca; otherwise, return None.

Why it works: The algorithm ensures that we only consider a node as LCA if both targets exist in its subtree. By propagating information about found nodes and candidate LCAs upwards, the correct lowest node is identified, and missing nodes are handled gracefully.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def dfs(node: 'TreeNode') -> tuple[bool, bool, 'TreeNode']:
            if not node:
                return False, False, None
            
            left_p, left_q, left_lca = dfs(node.left)
            right_p, right_q, right_lca = dfs(node.right)
            
            found_p = left_p or right_p or node == p
            found_q = left_q or right_q or node == q
            
            # If LCA already found in left or right, propagate it
            if left_lca:
                return found_p, found_q, left_lca
            if right_lca:
                return found_p, found_q, right_lca
            
            # If current node is LCA
            if (node == p or node == q) and (left_p or left_q or right_p or right_q):
                return found_p, found_q, node
            if left_p or left_q and right_p or right_q:
                return found_p, found_q, node
            
            return found_p, found_q, None
        
        found_p, found_q, lca = dfs(root)
        return lca if found_p and found_q else None

The code implements the DFS traversal described. Each recursive call determines whether p or q exists in the subtree and returns the LCA if found. This ensures we only return a node if both targets exist. The final return checks the flags to avoid returning an LCA when one node is missing.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    var dfs func(node *TreeNode) (bool, bool, *TreeNode)
    dfs = func(node *TreeNode) (bool, bool, *TreeNode) {
        if node == nil {
            return false, false, nil
        }
        
        leftP, leftQ, leftLCA := dfs(node.Left)
        rightP, rightQ, rightLCA := dfs(node.Right)
        
        foundP := leftP || rightP || node == p
        foundQ := leftQ || rightQ || node == q
        
        if leftLCA != nil {
            return foundP, foundQ, leftLCA
        }
        if rightLCA != nil {
            return foundP, foundQ, rightLCA
        }
        
        if (node == p || node == q) && (leftP || leftQ || rightP || rightQ) {
            return foundP, foundQ, node
        }
        if (leftP || leftQ) && (rightP || rightQ) {
            return foundP, foundQ, node
        }
        
        return foundP, foundQ, nil
    }
    
    foundP, foundQ, lca := dfs(root)
    if foundP && foundQ {
        return lca
    }
    return nil
}

The Go implementation mirrors the Python logic. Instead of returning tuples, we return multiple values (bool, bool, *TreeNode). Nil handling in Go replaces Python's None, and comparisons are straightforward using pointer equality.

Worked Examples

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

  1. Start DFS at node 3.
  2. Recurse left to node 5: left subtree contains 5, right contains 4 and 7; LCA candidate is 5.
  3. Recurse right to node 1: node 1 matches q; return (False, True, nil).
  4. Combine left and right results at node 3: left subtree has p, right subtree has q → LCA is 3.
  5. Both nodes found, return 3.

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

  1. DFS at node 3.
  2. DFS left to node 5: left subtree has 6, right subtree has 2 → DFS right to 2, which has left 7, right 4. Node 4 matches q.
  3. Combine results: node 5 has p itself and q in right subtree → LCA is 5.
  4. Return 5.

Example 3: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 10

  1. DFS reaches all nodes, finds p = 5, but q = 10 is never found.
  2. Final check fails found_q, return None.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is visited exactly once during DFS.
Space O(h) Recursive stack depth is the height of the