https://leetcode.com/problems/trim-a-binary-search-tree

This problem becomes easy when you understand the logic behind trimming.

  1. If we have value in node higher than high, then we need to cut this node and its right children (because it is BST), so we just return dfs(node.left).
  2. Similarly if value is less than low, we return dfs(node.right).
  3. Finally, if it is in between, we need to attach dfs(node.left) as left children and dfs(node.right) as right children and return our node, exactly this is meant by phrase “Trimming the tree should not change the relative structure of the elements that will remain in the tree”. So, if we need to delete some node, we need to reattach its children to its parent. One question I asked myself, if it is also possible to connect in this way? Answer is yes, because of BST structure, intuition is the following: you will never need to cut middle of the tree, see [4, 2, 5, 1, 3] tree, it is not possible to cut 2 out of this tree with keeping its stucture, because then root 4 must have 3 children. However it will never be the case, because if we need to cut 2 from tree, we either need to cut all number more than 2, or all numbers less than 2

Time complexity is O(n), where n is number of nodes and space is O(h), where h is heigth of tree.

 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)

If you like the solution, you can upvote it on leetcode discussion section: Problem 0669