Trim a Binary Search Tree

Medium
1927.

Trim a Binary Search Tree

Trim a Binary Search Tree is a medium coding problem on depth-first search, trees and recursion, asked in Amazon, Microsoft and Bloomberg interviews.

You are given the root of a binary search tree with distinct values and two integers low and high. Trim the tree so that every remaining value lies in the inclusive range [low, high].

Trimming must not change the relative structure of the nodes that remain: any node that stays keeps every remaining descendant as a descendant. The result is unique. Return the root of the trimmed tree, which may be different from the original root, or an empty tree.

Example 1

Input
root = [1,0,2], low = 1, high = 2
Output
[1,null,2]
Explanation
0 is below the range and is removed; 1 and 2 stay where they were.

Example 2

Input
root = [3,0,4,null,2,null,null,1], low = 1, high = 3
Output
[3,2,null,1]
Explanation
0 is too small, so its right subtree (2 with child 1) takes its place under 3; 4 is too large and has no children to keep.

Example 3

Input
root = [2,1,3], low = 4, high = 5
Output
[]
Explanation
Every value is below 4, so nothing survives.

Constraints

  • The number of nodes in the tree is in the range [1, 10^4]
  • 0 <= Node.val <= 10^4
  • The value of each node in the tree is unique
  • root is guaranteed to be a valid binary search tree
  • 0 <= low <= high <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} low
 * @param {number} high
 * @return {TreeNode}
 */
var trimBST = function(root, low, high) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Trim a Binary Search Tree — Solution in Python, Java & C++

Trim a Binary Search Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Trim a Binary Search Tree is a medium coding problem on depth-first search, trees and recursion, asked in Amazon, Microsoft and Bloomberg interviews.

Problem statement

You are given the root of a binary search tree with distinct values and two integers low and high. Trim the tree so that every remaining value lies in the inclusive range [low, high].

Trimming must not change the relative structure of the nodes that remain: any node that stays keeps every remaining descendant as a descendant. The result is unique. Return the root of the trimmed tree, which may be different from the original root, or an empty tree.

Example 1

Input: root = [1,0,2], low = 1, high = 2
Output: [1,null,2]
Explanation: 0 is below the range and is removed; 1 and 2 stay where they were.

Example 2

Input: root = [3,0,4,null,2,null,null,1], low = 1, high = 3
Output: [3,2,null,1]
Explanation: 0 is too small, so its right subtree (2 with child 1) takes its place under 3; 4 is too large and has no children to keep.

Example 3

Input: root = [2,1,3], low = 4, high = 5
Output: []
Explanation: Every value is below 4, so nothing survives.

Constraints

  • The number of nodes in the tree is in the range [1, 10^4]
  • 0 <= Node.val <= 10^4
  • The value of each node in the tree is unique
  • root is guaranteed to be a valid binary search tree
  • 0 <= low <= high <= 10^4

Hints for Trim a Binary Search Tree

  1. Hint 1

    If a node's value is below low, the node and its entire left subtree are below low too.

  2. Hint 2

    So for such a node, the answer is simply the trimmed version of its right subtree — and symmetrically for a value above high.

  3. Hint 3

    A node inside the range stays: trim its two subtrees recursively and reattach the results.

How to solve Trim a Binary Search Tree

The search-tree order lets a whole subtree be discarded at once: a node below low drags its left subtree with it, a node above high its right subtree. A recursive function that returns the trimmed root of any subtree expresses this directly.

Approach

  1. trim(node): if node is null, return null.
  2. If node.val < low, return trim(node.right).
  3. If node.val > high, return trim(node.left).
  4. Otherwise set node.left = trim(node.left) and node.right = trim(node.right), and return node.

Why it works

Every node in the left subtree of a node below low is smaller still, so none of them can remain; the trimmed right subtree, whose values are all greater than that node, takes its place under the same parent and keeps the order. In-range nodes keep their position and recurse, so remaining nodes keep their ancestor relations.

Complexity

  • Time — O(n)
  • Space — O(h) for the recursion

Pitfalls

  • A node out of range is not simply deleted: its valid subtree must be spliced into its place.
  • The root itself can be out of range — the new root is whatever the recursion returns.
  • The result can be empty.

Reference solution

Python

from typing import Optional

def trimBST(root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
    if root is None:
        return None
    if root.val < low:
        return trimBST(root.right, low, high)
    if root.val > high:
        return trimBST(root.left, low, high)
    root.left = trimBST(root.left, low, high)
    root.right = trimBST(root.right, low, high)
    return root

Java

public static TreeNode trimBST(TreeNode root, int low, int high) {
    if (root == null) return null;
    if (root.val < low) return trimBST(root.right, low, high);
    if (root.val > high) return trimBST(root.left, low, high);
    root.left = trimBST(root.left, low, high);
    root.right = trimBST(root.right, low, high);
    return root;
}

C++

TreeNode* trimBST(TreeNode* root, int low, int high) {
    if (!root) return nullptr;
    if (root->val < low) return trimBST(root->right, low, high);
    if (root->val > high) return trimBST(root->left, low, high);
    root->left = trimBST(root->left, low, high);
    root->right = trimBST(root->right, low, high);
    return root;
}

JavaScript

var trimBST = function(root, low, high) {
    if (root === null) return null;
    if (root.val < low) return trimBST(root.right, low, high);
    if (root.val > high) return trimBST(root.left, low, high);
    root.left = trimBST(root.left, low, high);
    root.right = trimBST(root.right, low, high);
    return root;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals