Robust LCA in BST
Finding the Lowest Common Ancestor (LCA) is a fundamental problem in tree data structures, with applications ranging from hierarchical data management to genetic research. In a Binary Search Tree (BST), the unique ordering property often allows for more efficient solutions compared to general binary trees. This problem challenges you to implement a robust LCA function that not only finds the LCA but also gracefully handles scenarios where one or both target nodes might not be present in the BST.
Implement the function robustLCAInBST that takes the root of a Binary Search Tree (BST) and two integer values, valP and valQ.
Your task is to:
valP and valQ both exist within the BST.valP or valQ (or both) are not found in the BST, the function must return null.valP and valQ are found, return the lowest common ancestor of the nodes with these values.
p and q as descendants (where we allow a node to be a descendant of itself).root: The root node of a Binary Search Tree. Node values are unique.valP: An integer representing the value of the first target node.valQ: An integer representing the value of the second target node.TreeNode object representing the Lowest Common Ancestor, or null if valP or valQ is not found in the BST.TreeNode.val values in the BST are unique.valP equals valQ, and a node with that value exists, then that node itself is considered its own LCA.root is null (an empty tree), it should always return null.Examples
Example 1
Input:
root = [6,2,8,0,4,7,9,null,null,3,5], valP = 2, valQ = 8
Output:
6
Note:
The node with value 6 is the LCA of nodes with values 2 and 8.
Example 2
Input:
root = [6,2,8,0,4,7,9,null,null,3,5], valP = 2, valQ = 4
Output:
2
Note:
The node with value 2 is the LCA of nodes with values 2 and 4 (2 is an ancestor of 4).
Example 3
Input:
root = [6,2,8,0,4,7,9,null,null,3,5], valP = 2, valQ = 10
Output:
null
Note:
The node with value 10 is not present in the BST, so no valid LCA can be found.
Example 4
Input:
root = [], valP = 1, valQ = 2
Output:
null
Note:
The BST is empty, so no LCA can be found.
Constraints
[0, 10^4].[-10^9, 10^9].TreeNode.val are unique.valP and valQ are integers within the range [-10^9, 10^9].Loading editor...