Tree traversals

A binary tree has nodes with a left and right child. Traversal is how you visit every node; the order you choose determines what you can compute. The three depth-first orders differ only in when you touch the current node relative to its children.

• Inorder (left, node, right): on a binary search tree this yields values in sorted order.
• Preorder (node, left, right): visits the root first — used to copy/serialize a tree.
• Postorder (left, right, node): children before parent — used to delete a tree or compute values that depend on subtrees (like height).
• Level-order (BFS): visit level by level using a queue — for shortest depth and level-based answers.

def inorder(node, out):
    if not node:
        return
    inorder(node.left, out)
    out.append(node.val)      # visit between children
    inorder(node.right, out)

def max_depth(node):
    if not node:
        return 0
    return 1 + max(max_depth(node.left), max_depth(node.right))