BinarySearch 0252 Cutting Binary Search Tree

Problem statement

https://binarysearch.com/problems/Cutting-Binary-Search-Tree/

Solution

Equal to Leetcode 0669. Trim a Binary Search Tree.

Complexity

It is O(n) for time and O(h) for additional space.

Code

class Solution:
    def solve(self, root, lo, hi):
        def dfs(node):
            if not node: return node
            if node.val > hi:
                return dfs(node.left)
            elif node.val < lo:
                return dfs(node.right)
            else:
                node.left  = dfs(node.left)
                node.right = dfs(node.right)
                return node
            
        return dfs(root)