Skip to Content

Trim a binary search tree

Home | Coding Interviews | Simple Data Structures | 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 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.

class Solution:
   def trimBST(self, root, low, high):
       def dfs(node):
           if not node: return node
           if node.val > high:
               return dfs(node.left)
           elif node.val < low:
               return dfs(node.right)
           else:
               node.left  = dfs(node.left)
               node.right = dfs(node.right)
               return node
           
       return dfs(root)

Posted by Jamie Meyer 22 days ago