algoadvance

Leetcode 669. Trim a Binary Search Tree

Problem Statement

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 original left child will be its left child, and the same rule applies for the right child). Return the root of the trimmed binary search tree.

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

Clarifying Questions

1. Should the solution maintain the properties of a BST after trimming?
   • Yes, the trimmed tree should still maintain the binary search tree properties.
2. What should be returned when no nodes lie within the range [low, high]?
   • In that case, return nullptr as there will be no valid nodes in the tree.
3. Is it guaranteed that the tree will be valid or should invalid cases be handled?
   • The problem guarantees that the input tree is a valid binary search tree, so no need to handle invalid cases.

Strategy

1. Recursive Approach:
   • Traverse the tree recursively and adjust pointers to trim nodes that fall outside the range.
   • If the current node’s value is less than low, then its left subtree (and the node itself) cannot be part of the trimmed tree. Thus, we should recur for the right subtree.
   • If the current node’s value is greater than high, then its right subtree (and the node itself) cannot be part of the trimmed tree. Thus, we should recur for the left subtree.
   • If the current node’s value lies within the range [low, high], then we need to recursively trim its left and right subtrees.
2. Base Case:
   • If the current node is nullptr, return nullptr.

Code

#include<iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (!root) return nullptr;
        
        // If the value of the current node is less than low, ignore the left subtree
        if (root->val < low) {
            return trimBST(root->right, low, high);
        }
        
        // If the value of the current node is greater than high, ignore the right subtree
        if (root->val > high) {
            return trimBST(root->left, low, high);
        }
        
        // If the current node's value is within the range, trim its left and right subtrees
        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);
        
        return root;
    }
};

Time Complexity

• Time Complexity: The time complexity is O(N), where N is the number of nodes in the binary search tree. This is because every node is visited once.

• Space Complexity: The space complexity is O(H), where H is the height of the tree. This accounts for the call stack in the recursion, which in the worst case (unbalanced tree) can go up to N, and in the best case (balanced tree) will be log(N).

This completes the approach to solve the problem of trimming a Binary Search Tree to fit within a given range [low, high].

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?