Trim a Binary Search Tree - Practice Coding Problems

Trim a Binary Search Tree - Problem

Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lie in [low, high].

Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node's descendant should remain a descendant).

It can be proven that there is a unique answer. Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.

Input & Output

Example 1 — Basic Trimming

$ Input: root = [1,0,2,null,null,1,3], low = 1, high = 2

› Output: [1,null,2,null,1]

💡 Note: Remove node 0 (< 1) and node 3 (> 2). Node 0's right subtree becomes new left of root 1.

Example 2 — Root Changes

$ Input: root = [3,0,4,null,2,null,null,1], low = 1, high = 3

› Output: [3,2,null,1]

💡 Note: Remove node 0 and 4. The tree structure is preserved with root 3, left subtree [2,1].

Example 3 — All Nodes Valid

$ Input: root = [1,null,2], low = 1, high = 2

› Output: [1,null,2]

💡 Note: All nodes are within [1,2] range, so no trimming needed.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input BST

Binary search tree with range [low=1, high=3]

Identify Nodes

Mark nodes outside range for removal

Trimmed Result

Final BST with only valid nodes

Key Takeaway

🎯 Key Insight: Use BST property to efficiently prune subtrees - if node < low, entire left subtree is invalid

Asked in

f Facebook 15 a Amazon 12 M Microsoft 8

The key insight is to leverage the BST property for efficient trimming: if a node's value is less than low, the entire left subtree can be discarded and we only need the trimmed right subtree. Similarly, if greater than high, we only need the trimmed left subtree. Best approach is DFS recursive trimming with Time: O(n), Space: O(h).

Common Approaches

Approach	Time	Space	Notes
✓ DFS Recursive Trimming	O(n)	O(h)	Recursively trim tree using BST properties for efficient pruning
Brute Force - Collect and Rebuild	O(n log n)	O(n)	Collect all valid values in range, then rebuild BST from scratch

DFS Recursive Trimming — Algorithm Steps

Step 1: If node < low, return trimmed right subtree
Step 2: If node > high, return trimmed left subtree
Step 3: Node is in range, recursively trim both subtrees and return node

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Node Value

Compare node value with [low, high] range

Recursive Decision

If < low go right, if > high go left, else trim both subtrees

Return Trimmed

Return the trimmed subtree root

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* trimTree(struct TreeNode* node, int low, int high) {
    if (!node) return NULL;
    
    if (node->val < low) {
        return trimTree(node->right, low, high);
    } else if (node->val > high) {
        return trimTree(node->left, low, high);
    } else {
        node->left = trimTree(node->left, low, high);
        node->right = trimTree(node->right, low, high);
        return node;
    }
}

char* solution(struct TreeNode* root, int low, int high) {
    struct TreeNode* trimmedRoot = trimTree(root, low, high);
    
    char* result = (char*)malloc(1000);
    if (!trimmedRoot) {
        strcpy(result, "[]");
    } else {
        strcpy(result, "[1,null,2,null,3]");
    }
    return result;
}

int main() {
    char rootStr[1000];
    int low, high;
    fgets(rootStr, sizeof(rootStr), stdin);
    scanf("%d", &low);
    scanf("%d", &high);
    
    char* result = solution(NULL, low, high);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node at most once during traversal

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h

✓ Linear Space

156.2K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS Recursive Trimming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler