Binary Search Tree: range search operation and delete one node operation

binary_search_tree.py

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""
class Solution:
    """
    @param root: The root of the binary search tree.
    @param k1 and k2: range k1 to k2.
    @return: Return all keys that k1<=key<=k2 in ascending order.
    """     
    def searchRange(self, root, k1, k2):
        if not root:
            return []
        
        stack = []
        ret = []
        while root:
            if root.val < k1:
                root = root.right
            elif root.val > k1:
                stack.append(root)
                root = root.left
            else:
                ret.append(k1)
                root = root.right
                break
        
        while stack or root:
            if root:
                stack.append(root)
                root = root.left
            else:
                root = stack.pop()
                if root.val <= k2:
                    ret.append(root.val)
                else:
                    break
                root = root.right
        return ret

    def removeNode(self, root, value):
        if not root:
            return

        dummy = prev = TreeNode(2**31 - 1)
        prev.left = root
        while root and root.val != value:
            prev = root
            if root.val < value:
                root = root.right
            else:
                root = root.left

        if not root:
            # could not find target node
            pass
        elif not root.left or not root.right:
            # single or no children
            if root.val < prev.val:
                prev.left = root.left or root.right
            else:
                prev.right = root.left or root.right
        else:
            # two children
            min_node, root.right = self.pop_min(root.right)
            min_node.left = root.left
            min_node.right = root.right
            if root.val < prev.val:
                prev.left = min_node
            else:
                prev.right = min_node
        return dummy.left
    
    def pop_min(self, root):
        dummy = prev = TreeNode(2**31 - 1)
        prev.left = root
        while root.left:
            prev = root
            root = root.left
        prev.left = root.right
        root.right = None
        return root, dummy.left