Augmented BST: Rank, Range Sum, and Deletion
At Meesho, efficiently managing and querying product catalog data is paramount. Imagine a scenario where product prices are stored in a Binary Search Tree (BST) for fast lookups. To support advanced analytical queries, such as finding the k-th cheapest product or calculating the total price of products within a specific price range, the standard BST needs to be augmented. This problem challenges you to implement an augmented BST that can handle these complex queries efficiently, including node deletions.
You are required to implement the AugmentedBST class. This class should manage a Binary Search Tree and provide the following functionalities:
AugmentedBST with a given TreeNode representing the root of an initial valid BST. It must correctly calculate and store augmentation data (size and sum) for all nodes in the initial tree.deleteNode(val: number): Deletes the node with the specified val from the BST. After deletion, the tree must remain a valid BST, and all augmentation data (size and sum) must be correctly updated for affected nodes.findKthSmallest(k: number): Returns the value of the k-th smallest element in the BST. k is 1-indexed.sumRange(low: number, high: number): Returns the sum of all node values v such that low <= v <= high.Your implementation must ensure that all operations are as efficient as possible for a BST, leveraging the augmented node properties.
TreeNode Definition:
class TreeNode {
val: number;
left: TreeNode | null;
right: TreeNode | null;
size: number; // Number of nodes in this subtree
sum: number; // Sum of values in this subtree
constructor(val: number, left?: TreeNode | null, right?: TreeNode | null) {
this.val = val;
this.left = left === undefined ? null : left;
this.right = right === undefined ? null : right;
this.size = 1; // Initial size
this.sum = val; // Initial sum
}
}
Class Definition:
class AugmentedBST {
private root: TreeNode | null;
constructor(root: TreeNode | null) { /* ... */ }
deleteNode(val: number): void { /* ... */ }
findKthSmallest(k: number): number | null { /* ... */ }
sumRange(low: number, high: number): number { /* ... */ }
}
constructor(root: TreeNode | null): Takes the root of an initial BST. This tree is guaranteed to be a valid BST. Your constructor must initialize size and sum properties for all nodes.deleteNode(val: number): void: Modifies the BST in-place. If the node val is not found, the tree remains unchanged.findKthSmallest(k: number): number | null: Returns the val of the k-th smallest node. Returns null if k is out of bounds (e.g., k <= 0 or k > total_nodes).sumRange(low: number, high: number): number: Returns the total sum of node values within the inclusive range [low, high]. If no nodes are in the range, return 0.val) in the BST are unique positive integers.k for findKthSmallest is 1-indexed (i.e., k=1 means the smallest element).Examples
Example 1
Input:
operations = ["AugmentedBST", "findKthSmallest", "sumRange", "deleteNode", "findKthSmallest", "sumRange"] params = [[ [5,3,8,2,4,7,9] ], [1], [4,8], [5], [1], [4,8]]
Output:
[null,2,24,null,2,19]
Note:
[5,3,8,2,4,7,9]. Root: 5.findKthSmallest(1): The smallest element is 2.sumRange(4,8): Nodes in range are 4, 5, 7, 8. Sum = 4 + 5 + 7 + 8 = 24.deleteNode(5): Node 5 is deleted. The BST re-arranges, typically replacing 5 with its inorder successor (7).
New tree (example structure): [7,3,8,2,4,null,9] (7 is new root, 5's left child 3 remains, 5's right child 8's left child 7 is gone, 8's right child 9 remains).findKthSmallest(1): The smallest element is still 2.sumRange(4,8): Nodes in range are 4, 7, 8. Sum = 4 + 7 + 8 = 19.Example 2
Input:
operations = ["AugmentedBST", "deleteNode", "findKthSmallest", "sumRange"] params = [[ [10,5,15,3,7,12,18] ], [10], [4], [1,100]]
Output:
[null,null,12,60]
Note:
[10,5,15,3,7,12,18]. Root: 10.deleteNode(10): Node 10 is deleted. The BST re-arranges, typically replacing 10 with its inorder successor (12).
New tree (example structure): [12,5,15,3,7,null,18].findKthSmallest(4): The elements in order are 3, 5, 7, 12, 15, 18. The 4th smallest is 12.sumRange(1,100): All remaining nodes are within this range: 3, 5, 7, 12, 15, 18. Sum = 3 + 5 + 7 + 12 + 15 + 18 = 60.Example 3
Input:
operations = ["AugmentedBST", "findKthSmallest", "deleteNode", "sumRange"] params = [[ [] ], [1], [5], [1,10]]
Output:
[null,null,null,0]
Note:
findKthSmallest(1): Tree is empty, returns null.deleteNode(5): Node 5 not found in empty tree, no change, returns null.sumRange(1,10): Tree is empty, sum is 0.Constraints
0 and 10^5.val, low, high) will be between 1 and 10^9.k will be between 1 and 10^5.val in the tree are unique.deleteNode (handling 0, 1, 2 children cases) while maintaining BST properties.size and sum properties across all operations.findKthSmallest (O(H) using size) and sumRange (O(H + M), where M is number of nodes in range).k out of bounds, and nodes not found.Loading editor...