Trees & BST

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def in_order(node, output):
    if node is None:
        return
    # Everything smaller than node lives to the left, so print it first.
    in_order(node.left, output)
    output.append(node.val)
    # Everything larger lives to the right, so it comes last.
    in_order(node.right, output)


def to_sorted_list(root):
    output = []
    in_order(root, output)
    return output

def search_bst(root, target):
    current = root
    while current is not None:
        if target == current.val:
            return current
        if target < current.val:
            # Everything to the right is larger than current, so the target
            # cannot possibly be over there. Discard that whole subtree.
            current = current.left
        else:
            current = current.right
    return None


def insert_into_bst(root, value):
    if root is None:
        return TreeNode(value)

    current = root
    while True:
        if value < current.val:
            if current.left is None:
                # We fell off the tree — this empty slot is where it belongs.
                current.left = TreeNode(value)
                return root
            current = current.left
        else:
            if current.right is None:
                current.right = TreeNode(value)
                return root
            current = current.right

def is_valid_bst(root):

    def check(node, low, high):
        if node is None:
            return True                 # an empty subtree is trivially valid

        # The node must sit strictly inside the window its ancestors left it.
        if node.val <= low or node.val >= high:
            return False

        # Going left tightens the ceiling; going right lifts the floor.
        left_ok = check(node.left, low, node.val)
        right_ok = check(node.right, node.val, high)
        return left_ok and right_ok

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

def is_valid_bst_inorder(root):
    stack = []
    current = root
    previous_value = None

    while current is not None or stack:
        # Dive as far left as possible, remembering the way back.
        while current is not None:
            stack.append(current)
            current = current.left

        current = stack.pop()            # this is the next value in sorted order
        if previous_value is not None and current.val <= previous_value:
            return False
        previous_value = current.val

        current = current.right

    return True

def height(node):
    """Number of nodes on the longest root-to-leaf path. Empty tree = 0."""
    if node is None:
        return 0
    left_height = height(node.left)
    right_height = height(node.right)
    return 1 + max(left_height, right_height)


def is_balanced(root):
    # Returns the real height, or -1 as a flag meaning "already unbalanced".
    # The flag is what keeps this O(n) instead of O(n^2).
    def height_or_flag(node):
        if node is None:
            return 0

        left_height = height_or_flag(node.left)
        if left_height == -1:
            return -1                    # bad news travels straight up

        right_height = height_or_flag(node.right)
        if right_height == -1:
            return -1

        if abs(left_height - right_height) > 1:
            return -1
        return 1 + max(left_height, right_height)

    return height_or_flag(root) != -1


def diameter_of_binary_tree(root):
    longest_path = 0                     # measured in EDGES, not nodes

    def height(node):
        nonlocal longest_path
        if node is None:
            return 0

        left_height = height(node.left)
        right_height = height(node.right)

        # A path through this node uses both arms, but a parent could only
        # ever use one — so record this here and return only the better arm.
        longest_path = max(longest_path, left_height + right_height)
        return 1 + max(left_height, right_height)

    height(root)
    return longest_path

def sorted_array_to_bst(numbers):

    def build(low, high):
        if low > high:
            return None

        # The middle element splits the slice into two halves of nearly equal
        # size — that even split is exactly what makes the tree balanced.
        middle = (low + high) // 2
        node = TreeNode(numbers[middle])
        node.left = build(low, middle - 1)
        node.right = build(middle + 1, high)
        return node

    return build(0, len(numbers) - 1)

def delete_node(root, key):
    if root is None:
        return None

    if key < root.val:
        root.left = delete_node(root.left, key)
    elif key > root.val:
        root.right = delete_node(root.right, key)
    else:
        # Found it. Case 1 and 2: zero or one child — promote the child.
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left

        # Case 3: two children. The in-order successor is the smallest value
        # in the right subtree, and it is the only value that can sit here
        # without breaking the invariant. Copy it up, then delete the original.
        successor = root.right
        while successor.left is not None:
            successor = successor.left
        root.val = successor.val
        root.right = delete_node(root.right, successor.val)

    return root