Smallest Strictly Bounded Subtree in a BST
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.
root of a Binary Search Tree (BST) and two integer values, val1 and val2.N satisfy val1 < N.val < val2.null.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).TreeNode representing the root of the smallest valid subtree, or null if none exists.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.val1 and val2 themselves are not included in the valid range.Examples
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.
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.
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.
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
N is between 0 and 10^4.TreeNode.val), val1, and val2 are integers between -10^9 and 10^9.TreeNode.val are unique.root can be null (representing an empty tree).Loading editor...