Frontend School

Conditional BST Lowest Common Ancestor

DSA
medium

Conditional BST Lowest Common Ancestor

Medium
Tree
Binary Search Tree
Lowest Common Ancestor

Overview

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.

What you need to do / Task

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:

  1. If both nodes with values p and q are present in the BST, return their LCA TreeNode.
  2. If only the node with value p is present, but the node with value q is not, return the TreeNode with value p.
  3. If only the node with value q is present, but the node with value p is not, return the TreeNode with value q.
  4. If neither the node with value 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 & output

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:

  • A TreeNode representing the smart LCA as per the rules above, or null if neither p nor q is found.

Clarifications

  • Empty Tree: If root is null, what should be returned? If the tree is empty, neither p nor q can be found, so null should be returned.
  • Duplicate Values: Node values in the BST are guaranteed to be unique.
  • Node Definition: Assume a standard TreeNode structure with val, left, and right properties.

Examples

1

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.

2

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.

3

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.

4

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

Constraints & assumptions

  • The number of nodes in the tree is in the range [0, 10^4].
  • Node values, p, and q are integers in the range [-10^9, 10^9].
  • The given tree is a valid Binary Search Tree (BST).
  • Node values are unique.
  • Time complexity target: O(H) where H is the height of the BST.
  • Space complexity target: O(1) for iterative solutions or O(H) for recursive solutions (due to recursion stack).

Out of scope

  • Validating if the input tree is a BST. Assume it's always valid.
  • Handling non-integer node values.

What interviewers evaluate

  • Correctness: Does the solution correctly handle all specified conditions (both present, one present, neither present) for LCA in a BST?
  • Efficiency: Is the solution optimized for time and space complexity, leveraging BST properties?
  • Edge Cases: Does the solution gracefully handle edge cases like an empty tree, p or q being the root, or p or q being an ancestor of the other?
  • Code Quality: Is the code clean, readable, well-structured, and easy to understand?

Loading editor...