Tree Traversal

Trees are everywhere in coding problems. There are four main ways to walk through them, and each reveals different information about the tree's structure.

The Four Traversals

Inorder (Left, Root, Right)

For BSTs, this gives sorted order:

def inorder(root):
    if not root:
        return
    inorder(root.left)
    print(root.val)  # Process
    inorder(root.right)

Preorder (Root, Left, Right)

Good for copying trees, prefix expressions:

def preorder(root):
    if not root:
        return
    print(root.val)  # Process first
    preorder(root.left)
    preorder(root.right)

Postorder (Left, Right, Root)

Good for deleting trees, calculating sizes:

def postorder(root):
    if not root:
        return
    postorder(root.left)
    postorder(root.right)
    print(root.val)  # Process last

Level-Order (BFS)

Visit level by level, left to right:

def levelOrder(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)

    return result