Frontend School

Robust LCA in BST

DSA
medium

Robust LCA in BST

Medium
Tree
Binary Search Tree
LCA
Recursion
Iteration

Overview

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.

What you need to do / Task

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:

  1. Determine if nodes with values valP and valQ both exist within the BST.
  2. If either valP or valQ (or both) are not found in the BST, the function must return null.
  3. If both valP and valQ are found, return the lowest common ancestor of the nodes with these values.
    • The LCA is defined as the lowest node in the tree that has both p and q as descendants (where we allow a node to be a descendant of itself).

Input & output

  • 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.
  • Return: A TreeNode object representing the Lowest Common Ancestor, or null if valP or valQ is not found in the BST.

Clarifications

  • All TreeNode.val values in the BST are unique.
  • If valP equals valQ, and a node with that value exists, then that node itself is considered its own LCA.
  • If the input root is null (an empty tree), it should always return null.

Examples

1

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.

2

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).

3

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.

4

Example 4

Input:

root = [], valP = 1, valQ = 2

Output:

null

Note:

The BST is empty, so no LCA can be found.

Constraints

Constraints & assumptions

  • The number of nodes in the tree is in the range [0, 10^4].
  • Node values are [-10^9, 10^9].
  • All TreeNode.val are unique.
  • The tree is guaranteed to be a valid BST.
  • valP and valQ are integers within the range [-10^9, 10^9].

Out of scope

  • You do not need to handle tree balancing or reconstruction. Assume the input BST is valid and correctly structured.

What interviewers evaluate

  • Correctly identifies the LCA in a BST by leveraging its structural properties.
  • Robustly handles edge cases, specifically when one or both target nodes are not present in the tree.
  • Demonstrates efficient algorithm design (time and space complexity).
  • Writes clear, readable, and idiomatic code.

Loading editor...