Trim A Binary Search Tree

  • Microsoft Interview Questions

Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.


/ \
3 6

L = 5 R = 7



We traverse through the whole tree while checking if the current node value < R or value > L. If first condition is not true then we conclude that the trim must occur to hte left of the node and vice-versa. If both conditions fail, then we have to trim both sides of the tree.



class Solution1 {
    public TreeNode trimBST(TreeNode root, int L, int R) {
        if (root == null) {
            return root;

        if (root.val > R) {
            return trimBST(root.left, L, R);

        if (root.val < L) {
            return trimBST(root.right, L, R);

        root.left = trimBST(root.left, L, R);
        root.right = trimBST(root.right, L, R);
        return root;

Complexity Analysis:

  • Time Complexity: O(N), where NN is the total number of nodes in the given tree.

  • Space Complexity: O(N).

Scroll to Top

Full Stack Integrated Bootcamp Free Trial

  • Please enter a number from 7000000000 to 9999999999.