algoadvance

Leetcode Problem 669: Trim a Binary Search Tree

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 descendants should remain as descendants). It can be proved 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.

Example:

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

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

Clarifying Questions:

  1. Tree definition: How is the tree structured in the input? Typically, it’s provided as a list or TreeNode objects in real-use scenarios.
  2. Return type: Do we return the modified tree’s root node or an array representation of the tree? (Likely, the root node of the trimmed tree).

Assumptions based on standard BST and Leetcode conventions:

Here’s the typical TreeNode class definition:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Strategy:

  1. Traverse the Tree: We will perform a traversal of the tree and for each node, we:
    • Check if the current node is within the [low, high] range:
      • If it is, we recursively trim the left and right subtrees.
      • If it is not, we choose to traverse a specific subtree (left if current node value is greater than high, right if less than low).
  2. Recursive Function: The function will modify the tree in place, ensuring nodes not within the range are removed and return the appropriately altered root.

Code:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def trimBST(root: TreeNode, low: int, high: int) -> TreeNode:
    if not root:
        return None
    
    if root.val < low:
        # Nodes from left subtree won't fall in the range
        return trimBST(root.right, low, high)
    
    if root.val > high:
        # Nodes from right subtree won't fall in the range
        return trimBST(root.left, low, high)
    
    # Node is within the range
    root.left = trimBST(root.left, low, high)
    root.right = trimBST(root.right, low, high)
    
    return root

Time Complexity

The time complexity of this solution is O(n), where n is the number of nodes in the tree, because in the worst case, we visit each node exactly once. The space complexity is O(h) where h is the height of the tree, considering the recursion stack space.

This recursive approach ensures that the tree is trimmed by directly addressing nodes only within the specified range [low, high], maintaining the BST properties, and making efficient cuts to the left and right subtrees when necessary.

Try our interview co-pilot at AlgoAdvance.com