Python Iterative solution using Pre-order traversal

  • 0

    This is like using the pre-order traversal iterative approach. Whenever we get a current node, it is already within the boundary (otherwise it is removed in a previous step). Then adjust the left & right children until they are within the range (or None). Push the right child if it is not None for future adjustment.

    A dummy node with infinite value is useful to avoid potential bugs.

    class Solution(object):
        def trimBST(self, root, L, R):
            :type root: TreeNode
            :type L: int
            :type R: int
            :rtype: TreeNode
            def out_of_bound(node):
                return not L <= node.val <= R
            dummy = TreeNode(float('inf'))
            dummy.left = root
            stack = []
            root = dummy
            while root or stack: # Same loop guards as pre-order traversal
                if not root:
                    root = stack.pop()
                    while root.left and out_of_bound(root.left): # Keep adjusting the left child
                        root.left = root.left.right if root.left.val < L else root.left.left
                    while root.right and out_of_bound(root.right): # Keep adjusting the right child
                        root.right = root.right.right if root.right.val < L else root.right.left
                    if root.right:
                        # Check the right subtree later
                    root = root.left
            return dummy.left

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.