We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Trim a Binary Search Tree

Number: 669

Difficulty: Medium

Paid? No

Companies: Amazon, Bloomberg

Problem Description

Given the root of a binary search tree and two integers low and high, trim the tree so that all its elements lie in the inclusive range [low, high]. The trimming process should not alter the relative structure of the remaining nodes (i.e., any node's descendant should remain its descendant). It is guaranteed that there is a unique answer. The new root of the tree may change based on the provided bounds.

Key Insights

  • If a node's value is less than low, then its left subtree will also be less than low due to the BST property and can be discarded.
  • If a node's value is greater than high, then its right subtree can be discarded.
  • Use depth-first search (DFS) recursively to trim both the left and right subtrees.
  • Maintain the original tree structure for the retained nodes.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes, since each node is visited once. Space Complexity: O(n) in the worst-case for the recursion call stack (O(log n) on average for a balanced tree).

Solution

The solution employs a recursive DFS approach on the binary search tree. For each node, we:

  1. Check if the current node is null; if it is, return null.
  2. If the node's value is smaller than low, move to its right subtree (since all nodes in its left subtree are automatically out of range).
  3. If the node's value is greater than high, move to its left subtree.
  4. Otherwise, recursively trim the left and right subtrees. This approach takes advantage of the BST properties to efficiently discard entire subtrees that are out of the allowed range without examining every node in those subtrees.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val         # Node's value
        self.left = left       # Left child pointer
        self.right = right     # Right child pointer

class Solution:
    def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
        # Base case: if node is None, return None.
        if not root:
            return None
        
        # If node's value is less than low, trim right subtree.
        if root.val < low:
            return self.trimBST(root.right, low, high)
        
        # If node's value is greater than high, trim left subtree.
        if root.val > high:
            return self.trimBST(root.left, low, high)
        
        # Otherwise, recursively trim left and right subtrees.
        root.left = self.trimBST(root.left, low, high)
        root.right = self.trimBST(root.right, low, high)
        return root
← Back to All Questions