LeetCode Solutions Blog

Lowest Common Ancestor of a Binary Tree II

Number: 1780

Difficulty: Medium

Paid? Yes

Problem Description

Given the root of a binary tree, find the lowest common ancestor (LCA) of two given nodes, p and q. A node can be a descendant of itself. If either p or q does not exist in the tree, return null.

Key Insights

Use a DFS (Depth-First Search) recursion to traverse the tree.
For each node, check if it is equal to p or q.
Recursively search the left and right subtrees.
If both left and right recursive calls return non-null values, the current node is the LCA.
To ensure both nodes exist in the tree, use flags (or count) when p or q are encountered during traversal.
If after the DFS traversal one of the nodes was not found, return null.

Space and Time Complexity

Time Complexity: O(n) where n is the number of nodes, since we traverse every node in the worst-case. Space Complexity: O(n) in the worst-case due to the recursion stack.

Solution

We perform a DFS recursion that checks each node to determine if it matches either p or q. While recursing, we record if p and q have been found using additional flags. At each node, if the left and right subtrees yield a non-null result, it means that the current node is the lowest common ancestor. After the DFS completes, we verify that both nodes were found. If either node is missing, we return null. This approach ensures that we get the true LCA only when both nodes exist in the tree.

Code Solutions

# 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':
        # Flags to check if p and q have been found
        self.foundP = False
        self.foundQ = False

        def dfs(node):
            if not node:
                return None

            # Search left and right subtrees
            left = dfs(node.left)
            right = dfs(node.right)

            # Check if current node is p or q
            mid = None
            if node == p or node == q:
                mid = node
                if node == p:
                    self.foundP = True
                if node == q:
                    self.foundQ = True

            # If any two of the three flags (mid, left, right) are non-null, node is LCA.
            if (mid is not None and left is not None) or (mid is not None and right is not None) or (left is not None and right is not None):
                return node

            # Return the non-null value among mid, left, and right.
            return mid if mid is not None else left if left is not None else right

        # Get potential LCA while traversing the tree
        lca = dfs(root)
        # If both nodes were found, return LCA; otherwise return None.
        return lca if self.foundP and self.foundQ else None