Frontend School

Augmented BST: Rank, Range Sum, and Deletion

DSA
hard

Augmented BST: Rank, Range Sum, and Deletion

Hard
Tree
BST
Data Structures

Overview

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.

What you need to do / Task

You are required to implement the AugmentedBST class. This class should manage a Binary Search Tree and provide the following functionalities:

  1. Constructor: Initializes the 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.
  2. 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.
  3. findKthSmallest(k: number): Returns the value of the k-th smallest element in the BST. k is 1-indexed.
  4. 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.

Input & output

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.

Clarifications

  • Node values (val) in the BST are unique positive integers.
  • k for findKthSmallest is 1-indexed (i.e., k=1 means the smallest element).
  • The initial BST passed to the constructor is always valid.

Examples

1

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:

  1. Initialize BST with [5,3,8,2,4,7,9]. Root: 5.
  2. findKthSmallest(1): The smallest element is 2.
  3. sumRange(4,8): Nodes in range are 4, 5, 7, 8. Sum = 4 + 5 + 7 + 8 = 24.
  4. 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).
  5. findKthSmallest(1): The smallest element is still 2.
  6. sumRange(4,8): Nodes in range are 4, 7, 8. Sum = 4 + 7 + 8 = 19.
2

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:

  1. Initialize BST with [10,5,15,3,7,12,18]. Root: 10.
  2. 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].
  3. findKthSmallest(4): The elements in order are 3, 5, 7, 12, 15, 18. The 4th smallest is 12.
  4. sumRange(1,100): All remaining nodes are within this range: 3, 5, 7, 12, 15, 18. Sum = 3 + 5 + 7 + 12 + 15 + 18 = 60.
3

Example 3

Input:

operations = ["AugmentedBST", "findKthSmallest", "deleteNode", "sumRange"] params = [[ [] ], [1], [5], [1,10]]

Output:

[null,null,null,0]

Note:

  1. Initialize an empty BST.
  2. findKthSmallest(1): Tree is empty, returns null.
  3. deleteNode(5): Node 5 not found in empty tree, no change, returns null.
  4. sumRange(1,10): Tree is empty, sum is 0.

Constraints

Constraints & assumptions

  • The number of nodes in the BST will be between 0 and 10^5.
  • Node values (val, low, high) will be between 1 and 10^9.
  • k will be between 1 and 10^5.
  • The initial tree provided to the constructor is always a valid BST.
  • All val in the tree are unique.

What interviewers evaluate

  • Correctness of BST Operations: Accurate implementation of deleteNode (handling 0, 1, 2 children cases) while maintaining BST properties.
  • Efficient Augmentation Management: Proper calculation and update of size and sum properties across all operations.
  • Algorithmic Efficiency: Optimal time complexity for findKthSmallest (O(H) using size) and sumRange (O(H + M), where M is number of nodes in range).
  • Edge Case Handling: Robustness in handling empty trees, k out of bounds, and nodes not found.

Loading editor...