LeetCode 669: Trim a Binary Search Tree Solution

Master LeetCode problem 669 (Trim a Binary Search Tree), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

669. Trim a Binary Search Tree

Medium

Tree Depth-First Search Binary Search Tree Binary Tree

Problem Explanation

Explanation:

To trim a binary search tree, we need to remove any nodes whose values fall outside the range [low, high]. Here's the algorithmic idea:

If the current node's value is outside the range [low, high], we need to trim it and recursively trim its left and right subtrees.
If the current node's value is within the range [low, high], we recursively trim its left and right subtrees.

Time Complexity: The time complexity of this algorithm is O(N), where N is the number of nodes in the tree.

Space Complexity: The space complexity of this algorithm is O(H), where H is the height of the tree.

Solution Code

class Solution {
    public 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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 669 (Trim a Binary Search Tree)?

This page provides optimized solutions for LeetCode problem 669 (Trim a Binary Search Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 669 (Trim a Binary Search Tree)?

The time complexity for LeetCode 669 (Trim a Binary Search Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 669 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 669 in Java, C++, or Python.

Back to LeetCode Solutions