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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Trim a Binary Search Tree

Difficulty: Medium

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

Key Insights

  • A binary search tree (BST) has the property that for each node, values in the left subtree are smaller, and values in the right subtree are larger.
  • The trimming process involves removing nodes that fall outside the specified [low, high] range.
  • If a node's value is less than low, we need to trim its left subtree and return its right child.
  • If a node's value is greater than high, we need to trim its right subtree and return its left child.
  • If a node's value is within the range, we recursively trim both subtrees and return the node itself.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of nodes in the tree since we may need to visit each node. Space Complexity: O(h) - where h is the height of the tree due to the recursion stack.

Solution

The solution uses a recursive depth-first search (DFS) approach to traverse the tree. At each node, we check its value against the low and high bounds:

  1. If the node's value is less than low, we recursively trim the right subtree.
  2. If the node's value is greater than high, we recursively trim the left subtree.
  3. If the node's value is within the range, we recursively trim both subtrees and return the current node.

This ensures that we maintain the structure of the remaining elements while removing nodes that fall outside the defined range.

Code Solutions

def trimBST(root, low, high):
    if not root:
        return None
    # If the current node's value is less than low,
    # we need to trim the left subtree and return the right
    if root.val < low:
        return trimBST(root.right, low, high)
    # If the current node's value is greater than high,
    # we need to trim the right subtree and return the left
    if root.val > high:
        return trimBST(root.left, low, high)
    # Current node is within the range, recursively trim both subtrees
    root.left = trimBST(root.left, low, high)
    root.right = trimBST(root.right, low, high)
    return root
← Back to All Questions