Trim a Binary Search Tree

Trim a Binary Search Tree

What is this problem about?

The "Trim a Binary Search Tree coding problem" involves modifying an existing Binary Search Tree (BST) so that all its elements fall within a given range [low, high]. Trimming means removing nodes that are outside the range while maintaining the BST properties. If a node's value is less than low, its entire left subtree must also be removed. If it's greater than high, its entire right subtree must be removed.

Why is this asked in interviews?

This "Trim a Binary Search Tree interview question" is a favorite at companies like Microsoft and Bloomberg because it tests your understanding of the core property of a BST: for any node, all values in the left subtree are smaller, and all values in the right subtree are larger. It evaluates your ability to use recursion to restructure a tree efficiently without creating new nodes unnecessarily.

Algorithmic pattern used

The "Binary Search Tree, Depth-First Search, Binary Tree, Tree interview pattern" is used here recursively.

1. If the current node is null, return null.
2. If root.val < low, the root and its left subtree are out of range. We return the result of trimming the right subtree.
3. If root.val > high, the root and its right subtree are out of range. We return the result of trimming the left subtree.
4. If the root is in range, we recursively trim its left and right children and return the root.

Example explanation

BST: 3 (root), 0 (left), 4 (right), 2 (right child of 0). Range: [1, 3].

1. Root(3): In range. Trim children.
2. Left Child(0): 0 < 1. Skip 0 and its left child. Trim its right child (2).
3. Node(2): In range. 2 becomes the new left child of 3.
4. Right Child(4): 4 > 3. Skip 4 and its right child. Final Tree: 3 (root), 2 (left).

Common mistakes candidates make

One major error in the "Trim a Binary Search Tree coding problem" is not correctly re-linking the nodes. Candidates often forget to update root.left and root.right with the results of the recursive calls. Another mistake is trying to handle the cases iteratively, which is much more complex for tree restructuring than a simple recursive approach.

Interview preparation tip

To excel in the "Binary Search Tree, Depth-First Search, Binary Tree, Tree interview pattern," focus on the "post-order" or "pre-order" nature of the transformation. In this case, we determine the fate of the current node before (or while) processing its children. Practice tree problems that require returning a modified TreeNode to get comfortable with this pattern.