Medium

Lowest Common Ancestor of a Binary Tree II

LAB

Return the lowest common ancestor value only if both p and q exist in the tree; otherwise return -1.

EXAMPLES

Example 1

Input
{
  "root": [
    3,
    5,
    1,
    6,
    2,
    0,
    8
  ],
  "p": 5,
  "q": 1
}

Output
3

FUNCTION SHAPE

root: intArrayp: intq: int→int

SOLUTION NOTE

Same as basic LCA but must verify both nodes exist. Track found_p/found_q flags. Only return result if both were found during traversal.

Reveal reference solution +

pythonREFERENCE

def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    self.found_p = False
    self.found_q = False

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

        left = dfs(node.left)
        right = dfs(node.right)

        if node == p:
            self.found_p = True
            return node
        if node == q:
            self.found_q = True
            return node

        if left and right:
            return node
        return left or right

    result = dfs(root)
    return result if self.found_p and self.found_q else None

TimeO(n)

SpaceO(h)

Open on LeetCode ↗