LeetCode 669 | Trim a Binary Search Tree | Python Solution

 Introduction:

In this blog post, we'll discuss a common problem in binary search trees, which is trimming a tree within a given range. We'll go over a Python solution using recursion to accomplish this task.

Problem Statement:

Given a binary search tree (BST) with the root node, low, and high values, the task is to trim the tree such that all the nodes' values are within the range [low, high]. You can assume that the given tree is a non-empty BST and the range low <= high.

Here's an example of a TreeNode class in Python that we'll be working with:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def trimBST(self, root, low, high):
        """
        :type root: TreeNode
        :type low: int
        :type high: int
        :rtype: TreeNode
        """
        def traverseTree(root , low , high ):
            if root is None:
                return None

            if root.val < low : # if root is lower than low then everything on left tree wiil be also lower based on BST property.
                return traverseTree(root.right , low ,high )
            elif root.val > high : #if root is higher that high value then everything on right tree will be also higher therefore we travel on left sub-tree
                return traverseTree(root.left , low ,high )
            else:
                root.left = traverseTree(root.left , low , high )
                root.right = traverseTree(root.right , low , high )

            return root 

        return traverseTree(root,low,high)

 

Explanation:

The traverseTree function is a helper function that takes the root, low, and high values as input. It performs the following steps:

1. If the root is None, return None.
2. If the root value is less than the low value, we know that all nodes in the left subtree will also be less than the low value due to the BST property. So, we only need to traverse the right subtree by calling traverseTree(root.right, low, high).
3. If the root value is greater than the high value, all nodes in the right subtree will also be greater than the high value. So, we only need to traverse the left subtree by calling traverseTree(root.left, low, high).
4. If the root value is within the range, we'll trim both the left and right subtrees by calling traverseTree recursively for the left and right child nodes.
5. Finally, we return the modified root node.

Conclusion:

In this blog post, we've discussed how to trim a binary search tree within a given range using a recursive function in Python. This solution effectively trims the tree while preserving its BST property, ensuring that the resulting tree is still a valid BST.