Tree traversals

A binary tree is a set of nodes where each node has a value and at most two children, left and right. The top node is the root; nodes with no children are leaves. A traversal visits every node exactly once in a defined order.

There are four orders interviewers expect. Preorder visits a node before its children (node, left, right). Inorder visits the left subtree, then the node, then the right subtree. Postorder visits both children before the node (left, right, node). Level order (breadth-first) visits the root, then every node at depth 1, then depth 2, and so on.

The first three are depth-first and are naturally written with recursion or an explicit stack. Level order uses a queue. Every traversal takes O(n) time; depth-first ones use O(h) extra space where h is the tree height, and level order uses O(w) where w is the widest level.

1. 1Pick the order based on when the node's own work must happen: before its children (preorder), between them (inorder), or after them (postorder).
2. 2Recursive depth-first traversal: if the node is empty, return. Otherwise make two recursive calls (left, then right) and do the node's work at the chosen point.
3. 3Iterative inorder: push nodes while walking left; when you cannot go left, pop a node, visit it, and move to its right child. Repeat until the stack is empty and the current node is empty.
4. 4Iterative preorder: push the root; pop a node, visit it, push its right child then its left child so the left is processed first.
5. 5Level order: put the root in a queue. While the queue is not empty, record its current size k, pop exactly k nodes (that is one level) and push their children for the next level.

from collections import deque

def preorder(node, out):              # fills out in place
    if node:
        out.append(node.val)          # node first
        preorder(node.left, out)
        preorder(node.right, out)

def inorder_iterative(root):
    out, stack, node = [], [], root
    while stack or node:
        while node:                   # go as far left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.val)
        node = node.right
    return out

def level_order(root):
    levels, q = [], deque([root] if root else [])
    while q:
        level = []
        for _ in range(len(q)):       # exactly the nodes of this level
            node = q.popleft()
            level.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        levels.append(level)
    return levels

Nodes have val, left and right fields (see the TreeNode class on the BST page). Recursive preorder shows the shape every depth-first traversal shares; moving the append gives inorder or postorder. The iterative inorder uses a stack to replace the call stack. Level order snapshots the queue size so each inner loop handles exactly one level. All run in O(n) time.

Cost: All traversals are O(n) time. Depth-first uses O(h) space (O(log n) balanced, O(n) skewed); level order uses O(w), up to about n/2 for a complete tree.