Conditional BST Lowest Common Ancestor
At OYO, managing property hierarchies and user preference trees efficiently is crucial for delivering a seamless experience. Imagine a system where property attributes (like amenities, room types) are organized in a Binary Search Tree (BST) for quick lookups and range queries. Sometimes, we need to find a common parent for two related attributes, but the attributes themselves might not always be present in the current tree state due to updates or regional variations. This problem challenges you to implement a robust function to find the "smart" lowest common ancestor under these dynamic conditions.
Implement a function findSmartLCA that takes the root of a Binary Search Tree (BST) and two integer values, p and q, representing the values of the nodes we are interested in. Your function should return the Lowest Common Ancestor (LCA) of nodes with values p and q if both are present in the BST. However, the requirement is more nuanced:
p and q are present in the BST, return their LCA TreeNode.p is present, but the node with value q is not, return the TreeNode with value p.q is present, but the node with value p is not, return the TreeNode with value q.p nor the node with value q is present in the BST, return null.You will be given the definition of a TreeNode class.
Input:
root: A TreeNode representing the root of a Binary Search Tree. The BST is guaranteed to be valid.p: An integer representing the value of the first target node.q: An integer representing the value of the second target node.Output:
TreeNode representing the smart LCA as per the rules above, or null if neither p nor q is found.root is null, what should be returned? If the tree is empty, neither p nor q can be found, so null should be returned.TreeNode structure with val, left, and right properties.Examples
Example 1
Input:
root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output:
6
Note:
Both nodes with values 2 and 8 are present in the BST. Their lowest common ancestor is the node with value 6.
Example 2
Input:
root = [6,2,8,0,4,7,9,null,null,3,5], p = 4, q = 1
Output:
4
Note:
The node with value 4 is present in the BST, but the node with value 1 is not. According to the rules, we return the present node, which is 4.
Example 3
Input:
root = [6,2,8,0,4,7,9,null,null,3,5], p = 1, q = 10
Output:
null
Note:
Neither the node with value 1 nor the node with value 10 are present in the BST. According to the rules, we return null.
Example 4
Input:
root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 3
Output:
2
Note:
Both nodes with values 2 and 3 are present. Node 2 is an ancestor of node 3, making 2 their LCA.
Constraints
[0, 10^4].p, and q are integers in the range [-10^9, 10^9].p or q being the root, or p or q being an ancestor of the other?Loading editor...