Binary Trees and Traversals

What even is a binary tree?

Here is a pop quiz: you have written a max(a, b) call. That is a binary tree. Root is max, left child is a, right child is b. You have used a tree.

A binary tree is any structure where:

1. There is one root node.
2. Every node has at most a left child and a right child — zero, one, or two, never more.
3. There are no cycles, and every non-root node has exactly one parent.

That is the whole definition. Nothing about ordering. Nothing about balance. Just: one root, two child slots per node, no loops. The moment you add an ordering rule ("left < root < right") you have a binary search tree. Right now we are staying general, because the traversal patterns you need to learn first have nothing to do with ordering.

flowchart TD
    A["40\n(root)"] --> B["20"]
    A --> C["60"]
    B --> D["10"]
    B --> E["30"]
    C --> F["50"]
    C --> G["70"]
    style A fill:#7c5cff,color:#fff
    style B fill:#22d3ee,color:#0a0a0f
    style C fill:#22d3ee,color:#0a0a0f
    style D fill:#00ff9d,color:#0a0a0f
    style E fill:#00ff9d,color:#0a0a0f
    style F fill:#00ff9d,color:#0a0a0f
    style G fill:#00ff9d,color:#0a0a0f

A few vocabulary words worth locking in, because interviewers throw them around:

• Height of a node: the number of edges on the longest downward path from that node to a leaf. Height of the whole tree = height of the root.
• Depth of a node: the number of edges from the root down to that node. Root has depth 0.
• Leaf: a node with no children.
• Full tree: every node has 0 or 2 children — no node has exactly one child.
• Complete tree: every level is filled left-to-right, with only the last level potentially incomplete. This is the shape a heap maintains.
• Perfect tree: full AND complete. Every internal node has two children, all leaves at the same depth. A perfect tree with height h has exactly 2^(h+1) - 1 nodes.

The distinction between these matters because balance governs performance. A balanced tree of n nodes has height O(log n). A degenerate tree (every node has one child — basically a linked list) has height O(n). Every tree operation's cost scales with height, so a skewed tree silently degrades O(log n) expectations into O(n) reality. This is the whole motivation behind AVL trees, red-black trees, and why you need the heap's complete-tree invariant.

The recursive mindset: the key that unlocks everything

Before showing you the four traversals, here is the mental model that makes all of them obvious rather than memorized.

A binary tree is recursively defined. In code, a node looks like this:

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

A "tree" is either None (an empty tree) or a TreeNode whose left and right are themselves trees. The structure calls itself. And that means any function over a tree can call itself on the left subtree and the right subtree, and the base case is just None.

The skeleton is always:

def solve(node):
    if node is None:          # base case: empty subtree
        return ...            # some identity value (0, True, None, [], ...)
    
    left_result  = solve(node.left)   # recurse left
    right_result = solve(node.right)  # recurse right
    
    return combine(node.val, left_result, right_result)

Nearly every tree problem on LeetCode fits this shape. Height of a tree? combine = 1 + max(left, right). Count nodes? combine = 1 + left + right. Check if balanced? combine = abs(left_height - right_height) <= 1 and left_ok and right_ok. The skeleton does not change. Only combine changes.

The four traversals are all just different choices of when to process the current node relative to the recursive calls. That is literally the only difference.

See crash course: recursion if you want to build this intuition from the ground up first — it is worth it.

The four traversals

Depth-first: inorder, preorder, postorder

All three are DFS. They visit every node exactly once, so they are all O(n) time and O(h) space (where h is height — the call stack can go as deep as the tree is tall).

Inorder — left → root → right

def inorder(node):
    if node is None:
        return []
    return inorder(node.left) + [node.val] + inorder(node.right)

For a binary search tree, inorder always yields a sorted sequence — that is its killer property. For a generic tree, it gives you the "flattened" left subtree, then the root, then the right subtree. Used for: BST validation, sorted iteration, expression tree evaluation.

Preorder — root → left → right

def preorder(node):
    if node is None:
        return []
    return [node.val] + preorder(node.left) + preorder(node.right)

The root comes out first, before anything else. Used for: copying/serializing a tree (you need to know the root before you can reconstruct children), generating prefix expressions, printing directory structures (folder name before its contents).

Postorder — left → right → root

def postorder(node):
    if node is None:
        return []
    return postorder(node.left) + postorder(node.right) + [node.val]

The root comes out last, after both subtrees are fully processed. Used for: deleting a tree (free children before the parent), evaluating expression trees bottom-up, computing subtree sizes and heights (you need children's answers before you can compute the parent's).

Here is the mnemonic that actually works: the name tells you when the root is visited — preorder visits root before children, postorder visits root after children, inorder visits root in between children.

{ "type": "bst", "title": "Inorder walk: left → root → right (yields sorted order for a BST)", "data": [40, 20, 60, 10, 30, 50, 70] }

Step through the inorder traversal on this tree. The output order is 10, 20, 30, 40, 50, 60, 70 — sorted, because this tree happens to be a valid BST. Watch how the call stack descends to the leftmost leaf before visiting anything.

Iterative inorder (the stack trick interviewers love)

The recursive versions above are clean to write, but sometimes you need an iterative version — either to avoid stack-overflow on deep trees or because the interviewer explicitly asks for it. Here is inorder iteratively, using an explicit stack:

def inorder_iterative(root):
    result = []
    stack = []
    curr = root

    while curr or stack:
        # Go as far left as possible
        while curr:
            stack.append(curr)
            curr = curr.left
        
        # Process the node
        curr = stack.pop()
        result.append(curr.val)
        
        # Move to right subtree
        curr = curr.right

    return result

The pattern: push nodes as you go left, pop and process when you can't go further left, then pivot to the right subtree. This is the exact same traversal order as the recursive version — just with an explicit stack instead of the call stack.

Level-order: BFS with a queue

The three DFS traversals all go deep first — down a branch before backtracking. Level-order goes wide first: all nodes at depth 0, then all nodes at depth 1, then depth 2, and so on. This is breadth-first search on a tree.

You cannot do this cleanly with recursion. You need a queue.

from collections import deque

def level_order(root):
    if root is None:
        return []
    
    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)      # how many nodes are on this level
        current_level = []

        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(current_level)

    return result

This returns [[40], [20, 60], [10, 30, 50, 70]] for our example tree — each level as its own list. The level_size snapshot at the start of the outer loop is the key move: it tells you how many nodes belong to the current level before you start adding their children.

When do you reach for level-order over DFS?

• Finding the minimum depth (shortest path to a leaf) — BFS reaches the shallowest leaf first, no need to explore the whole tree.
• Printing or serializing the tree level by level.
• Finding all nodes at a specific depth.
• The right side view of a tree (last node on each level).
• Zigzag traversal (alternate left-to-right and right-to-left per level).

Anything that involves "levels" or "the closest X" is almost always BFS. Anything that involves "all paths", "subtree structure", or "computing a value from children" is almost always DFS.

Complexity: the height problem

Traversal	Time	Space	Notes
Inorder (recursive)	O(n)	O(h)	call stack depth = height
Preorder (recursive)	O(n)	O(h)	same
Postorder (recursive)	O(n)	O(h)	same
Level-order (BFS)	O(n)	O(w)	w = max width ≈ n/2 at last level for a perfect tree

The O(h) space for DFS and O(w) for BFS look different, but for a balanced tree they are the same order of magnitude: h = O(log n) and the last level holds n/2 nodes, so w = O(n). For space purposes, balanced-tree BFS and DFS are both fine. For a degenerate skewed tree, DFS space blows up to O(n) (the call stack hits every node), while BFS stays O(1) since each level has one node.

A full worked example: diameter of a binary tree

The diameter of a tree is the length of the longest path between any two nodes (the path may or may not pass through the root). This is a good representative problem because the naive approach is obvious but wrong, and fixing it requires understanding postorder.

def diameter_of_binary_tree(root):
    # We need the height of each subtree AND we need to update the
    # diameter as we go — this is postorder: handle children first.
    
    max_diameter = 0

    def height(node):
        nonlocal max_diameter
        if node is None:
            return 0
        
        left_h  = height(node.left)    # postorder: left first
        right_h = height(node.right)   # then right
        
        # The longest path through this node = left_height + right_height
        max_diameter = max(max_diameter, left_h + right_h)
        
        return 1 + max(left_h, right_h)  # height of this subtree

    height(root)
    return max_diameter

The subtle insight: you cannot compute the diameter at the root and call it done — the longest path might go through any node in the tree. So you run the height recursion (which is postorder — you need child heights before computing the current node's height) and update a running max at every node. Single O(n) pass, O(h) space.

This is a template. Swap max_diameter for "path sum" and you get maximum path sum. Swap for a count of valid paths and you get path sum equals target. Same skeleton, different accumulator.

Common pitfalls

Forgetting the null base case. Every recursive tree function needs to handle node is None first, or you will get an AttributeError the moment you hit a leaf's missing child. Do not skip this even when it seems obvious.

Assuming inorder output is sorted. It is — but only for a binary search tree. For an arbitrary binary tree, inorder gives you one particular traversal order, nothing more. Do not conflate generic binary trees with BSTs.

Confusing height and depth. Height measures from a node down to the farthest leaf. Depth measures from the root down to the node. They use the same word "down" and trip people up constantly. Height of root = height of tree. Depth of root = 0.

Stack overflow on skewed trees. A linked-list-shaped tree of 100,000 nodes will blow Python's default recursion limit (~1000 frames). In an interview, mention you know this and would use an iterative approach with an explicit stack for production code. In Python specifically, you can also raise the limit with sys.setrecursionlimit, but that is a hack, not a fix.

Using BFS when you meant DFS (or vice versa). If the problem asks for "all root-to-leaf paths", BFS makes this annoying because you have to carry partial paths in the queue. DFS (preorder) is the natural fit. Conversely, "minimum depth" with DFS requires visiting the whole tree; BFS finds it immediately when the first leaf dequeues.

When NOT to use a generic binary tree

A plain binary tree with no structural guarantees is rarely what you want in production code. It is mainly a conceptual foundation and an interview substrate. Once you know what you need:

• Need fast O(log n) search, insert, delete? Use a binary search tree — the ordering invariant is what makes those operations fast.
• Always need the min or max element? Use a heap — it is a complete binary tree with a weaker but cheaper invariant than a BST.
• Need multi-level lookups (like a filesystem)? A general n-ary tree, trie, or B-tree is likely a better fit.

The generic binary tree is not a production data structure so much as a problem type. Almost every "tree problem" in an interview is really asking: "do you understand recursion on a hierarchical structure?" Answer yes convincingly, and the rest is pattern recognition.

The patterns, in short: inorder for sorted iteration / BST validation, preorder for copying / serialization, postorder for bottom-up aggregation, level-order for level-aware or shortest-path problems. Master the recursive skeleton solve(node) → combine(solve(left), solve(right)) and you will recognize the variation each problem needs in under a minute.