Solution: Trim a Binary Search Tree

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #669 (Medium): Trim a Binary Search Tree

---

Description:

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 lies 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.

---

Examples:

Example 1:
Input:	root = [1,0,2], low = 1, high = 2
Output:	[1,null,2]
Visual:

Example 2:
Input:	root = [3,0,4,null,2,null,null,1], low = 1, high = 3
Output:	[3,2,null,1]
Visual:

Example 3:
Input:	root = [1], low = 1, high = 2
Output:	[1]

Example 4:
Input:	root = [1,null,2], low = 1, high = 3
Output:	[1,null,2]

Example 5:
Input:	root = [1,null,2], low = 2, high = 4
Output:	[2]

---

Constraints:

• The number of nodes in the tree 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

---

Idea:

Any time you have a binary tree problem, it's a good idea to see if there's a recursive solution; all you need to do is to be able to define what you should at a random node and then ask if that holds true for all nodes.

In this situation, all we're doing is collapsing any branches that fall outside our given range from low L to high H, which should be simple enough.

The first thing we almost always need to deal with in a recursive function is the endpoint, so if root R is null, we should stop the recursion and return R back up. Then, we have a branch, depending on whether or not the value of R is < L or > H. If the value is too low, we want to pull up the branch to the right and continue the recursion, and vice versa if the value is too high. Otherwise, we just want to continue the recursion down each branch.

This approach is simple in execution and transitions very easily from language to language with very little differences.

---

Java Code:

class Solution {
    public TreeNode trimBST(TreeNode R, int L, int H) {
        if (R == null) return R;
        if (R.val < L) return trimBST(R.right,L,H);
        else if (R.val > H) return trimBST(R.left,L,H);
        R.left = trimBST(R.left,L,H) ;
        R.right = trimBST(R.right,L,H);
        return R;
    }
}

---

Python Code:

class Solution:
    def trimBST(self, R: TreeNode, L: int, H: int) -> TreeNode:
        if not R: return R
        if R.val < L: return self.trimBST(R.right,L,H)
        elif R.val > H: return self.trimBST(R.left,L,H)
        R.left = self.trimBST(R.left,L,H)
        R.right = self.trimBST(R.right,L,H)
        return R

---

C++ Code:

class Solution {
public:
    TreeNode* trimBST(TreeNode* R, int L, int H) {
        if (!R) return R;
        if (R->val < L) return trimBST(R->right,L,H);
        else if (R->val > H) return trimBST(R->left,L,H);
        R->left = trimBST(R->left,L,H) ;
        R->right = trimBST(R->right,L,H);
        return R;
    }
};

---

Javascript Code:

var trimBST = function(R, L, H) {
    if (!R) return R
    if (R.val < L) return trimBST(R.right,L,H)
    else if (R.val > H) return trimBST(R.left,L,H)
    R.left = trimBST(R.left,L,H) 
    R.right = trimBST(R.right,L,H)
    return R
};