def traverse(root):
    if not root: return
    # preorder actions
    traverse(root.left)
    # inorder actions
    traverse(root.val)
    # postorder actions

# For example, in-order traverse to a list
def inorder(root):
    return inorder(root.left) + [root.val] + inorder(root.right) if root else []

def traverse(root):
    result = {}
    queue = deque([(root, 0)])
    while queue:
        node, level = queue.popleft()
        queue.append((node.left, level + 1))
        queue.append((node.right, level + 1))
        result.setdefault(level, []).append(node.val)
    return result

def isValidBST(self, root: TreeNode) -> bool:
    if root is None: return True

    stack = [(root, float("-inf"), float("inf")), ]
    while stack:
        root, lower, upper = stack.pop()
        if not root:
            continue
        val = root.val
        if val <= lower or val >= upper:
            return False
        stack.append((root.left, lower, val))
        stack.append((root.right, val, upper))
    return True

def isValidBST(self, root: TreeNode) -> bool:
    def is_valid(root, lower, upper):
        if not root: return True
        if root.val <= lower or root.val >= upper:
            return False

        return is_valid(root.left, lower, root.val) \
                and is_valid(root.right, root.val, upper)

    return is_valid(root, float("-inf"), float("inf"))

def searchBST(self, root: TreeNode, val: int) -> TreeNode:
    if not root: return None
    if val == root.val: return root
    elif val < root.val: 
        return self.searchBST(root.left, val)
    else:  # val > root.val
        return self.searchBST(root.right, val)

def searchBST(self, root: TreeNode, val: int) -> TreeNode:
    if not root: return None
    while root and root.val != val:
        if val < root.val:
            root = root.left
        else:
            root = root.right
    return root

class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root: return TreeNode(val)
        if val < root.val:
            root.left = self.insertIntoBST(root.left, val)
        else:
            root.right = self.insertIntoBST(root.right, val)
        return root

class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        node = root
        while node:
            # insert into the right subtree
            if val > node.val:
                # insert right now
                if not node.right:
                    node.right = TreeNode(val)
                    return root
                else:
                    node = node.right
            # insert into the left subtree
            else:
                # insert right now
                if not node.left:
                    node.left = TreeNode(val)
                    return root
                else:
                    node = node.left
        return TreeNode(val)

def successor(root):
    root = root.right
    while root.left:
        root = root.left
    return root

def predecessor(root):
    root = root.left
    while root.right:
        root = root.right
    return root