Frontend School

Smallest Strictly Bounded Subtree in a BST

DSA
hard

Smallest Strictly Bounded Subtree in a BST

Hard
Tree
Binary Search Tree
Recursion
Depth-First Search

Overview

In large-scale data systems, efficiently querying and filtering data within specific ranges is crucial. For tree-structured data like a Binary Search Tree (BST), this often involves identifying relevant sub-structures. This problem challenges you to find the most compact subtree that satisfies a strict value range constraint.

What you need to do / Task

  1. Given the root of a Binary Search Tree (BST) and two integer values, val1 and val2.
  2. Find the root of the smallest (i.e., containing the minimum number of nodes) subtree such that all node values within this subtree N satisfy val1 < N.val < val2.
  3. If multiple such subtrees exist with the same minimum size, any one of them is acceptable.
  4. If no such subtree exists, return null.

Input & output

  • root: A TreeNode representing the root of a Binary Search Tree. Each TreeNode has an integer val, a left child, and a right child.
  • val1: An integer representing the lower bound (exclusive).
  • val2: An integer representing the upper bound (exclusive).
  • Return: A TreeNode representing the root of the smallest valid subtree, or null if none exists.

Clarifications

  • val1 can be greater than or equal to val2. In such cases, no node can satisfy val1 < N.val < val2, so the result should be null.
  • The values val1 and val2 themselves are not included in the valid range.
  • A single node can form a valid subtree if its value falls within the range.
  • The input tree is guaranteed to be a valid BST.

Examples

1

Example 1

Input:

root = [10,5,15,2,7,12,18], val1 = 6, val2 = 13

Output:

[7]

Note:

The tree is: 10(5(2,7),15(12,18)). Nodes '7' and '12' are single-node subtrees that fall within the range (6, 13). Both have a size of 1. The subtree rooted at '5' contains '2', which is out of range. The subtree rooted at '10' contains '5' and '15', which are out of range. '7' is one of the smallest valid subtrees.

2

Example 2

Input:

root = [8,4,12,2,6,10,14,1,3,5,7,9,11,13,15], val1 = 3, val2 = 13

Output:

[6,5,7]

Note:

The range is (3, 13). The subtree rooted at '6' ([6,5,7]) has all its nodes (5, 6, 7) within this range, and has a size of 3. The subtree rooted at '10' ([10,9,11]) also has all its nodes (9, 10, 11) within this range and a size of 3. These are the smallest valid subtrees. Any one of them is acceptable.

3

Example 3

Input:

root = [10,5,15,2,7,12,18], val1 = 10, val2 = 10

Output:

null

Note:

The range (10, 10) is empty, meaning no node value can satisfy 10 < N.val < 10. Therefore, no valid subtree exists.

4

Example 4

Input:

root = [10,5,15], val1 = 6, val2 = 9

Output:

null

Note:

The nodes in the tree are 5, 10, 15. None of these values are strictly between 6 and 9. Thus, no valid subtree can be formed.

Constraints

Constraints & assumptions

  • The number of nodes in the BST N is between 0 and 10^4.
  • Node values (TreeNode.val), val1, and val2 are integers between -10^9 and 10^9.
  • All TreeNode.val are unique.
  • The input root can be null (representing an empty tree).

Out of scope

  • Validating the input tree structure (assume it's a valid BST).
  • Handling non-integer values.

What interviewers evaluate

  • Correct application of BST properties to efficiently prune search space.
  • Ability to correctly identify valid subtrees and determine their size.
  • Optimal time and space complexity, avoiding redundant computations.
  • Clear, well-structured code with appropriate handling of edge cases.

Loading editor...