Practice/Amazon/Leetcode 1644. Lowest Common Ancestor of a Binary Tree II

Leetcode 1644. Lowest Common Ancestor of a Binary Tree II

CodingMust

Problem

You are given the root of a binary tree and two integer values representing target nodes p and q. Your task is to find and return the lowest common ancestor (LCA) of these two nodes, but with an important condition: both nodes must exist in the tree. If either node is missing from the tree, return null.

The lowest common ancestor is defined as the deepest node in the tree that has both p and q as descendants (where a node can be a descendant of itself).

The key challenge here is to efficiently verify that both target nodes exist in the tree while simultaneously computing their LCA in a single tree traversal.

Requirements

1. Return the TreeNode that represents the lowest common ancestor of p and q if both nodes exist
2. Return null if either p or q (or both) do not exist in the tree
3. A node can be considered an ancestor of itself
4. The tree nodes contain integer values, and p and q represent the values (not references to nodes)
5. All node values in the tree are unique

Constraints

• The number of nodes in the tree is in the range [0, 10^4]
• -10^9 ≤= Node.val ≤= 10^9
• -10^9 ≤= p, q ≤= 10^9
• p and q are different values

Examples

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3. Both nodes exist in the tree.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 10 Output: null Explanation: Node with value 10 does not exist in the tree, so we return null.

Example 3:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 2 Output: 5 Explanation: The LCA of nodes 5 and 2 is 5, since a node can be an ancestor of itself. Both nodes exist.

Example 4:

Input: root = [], p = 1, q = 2 Output: null Explanation: The tree is empty, so neither node exists.