Binary Trees & Traversals

A binary tree is a node-based structure where every node has at most two children, conventionally called left and right. Unlike a linked list, a tree branches — which means "visit every node" has more than one sensible order. This lesson codes the TreeNode class and all four standard traversals against one fixed example tree, so you can check your own understanding against exact expected output.

The TreeNode Class

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

The Example Tree Used In This Lesson

Every traversal below runs against this exact tree, so you can verify each output sequence yourself:

# Building the example tree used throughout this lesson
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)

Inorder Traversal (Left, Node, Right)

def inorder(node, result):
    if node is None:
        return                       # base case
    inorder(node.left, result)       # visit left subtree first
    result.append(node.val)          # then this node
    inorder(node.right, result)      # then right subtree

output = []
inorder(root, output)
print(output)

Output on the example tree: [4, 2, 5, 1, 3, 6]

Time complexity: O(n) — every node is visited exactly once. Space complexity: O(h) — the recursion stack depth equals the tree's height h (in the worst case, a completely skewed tree, h = n).

Preorder Traversal (Node, Left, Right)

def preorder(node, result):
    if node is None:
        return
    result.append(node.val)          # visit this node first
    preorder(node.left, result)
    preorder(node.right, result)

output = []
preorder(root, output)
print(output)

Output on the example tree: [1, 2, 4, 5, 3, 6]

Time complexity: O(n) — every node visited once. Space complexity: O(h) — recursion stack bounded by tree height.

Postorder Traversal (Left, Right, Node)

def postorder(node, result):
    if node is None:
        return
    postorder(node.left, result)
    postorder(node.right, result)
    result.append(node.val)          # visit this node last

output = []
postorder(root, output)
print(output)

Output on the example tree: [4, 5, 2, 6, 3, 1]

Time complexity: O(n) — every node visited once. Space complexity: O(h) — recursion stack bounded by tree height.

Level-Order Traversal (BFS, Using collections.deque)

The three traversals above are all DFS (depth-first search) — they plunge all the way down one branch before backtracking. Level-order traversal is different: it visits every node at depth 0, then every node at depth 1, then depth 2, and so on. That breadth-first behavior needs a queue, not the call stack. Python's plain list can act as a queue via .pop(0), but that's O(n) per removal since every remaining element has to shift down — for a real queue, use collections.deque, whose popleft() is O(1).

from collections import deque

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

    queue = deque([root])                    # enqueue the root first

    while queue:
        current = queue.popleft()             # dequeue the next node to visit -- O(1)
        result.append(current.val)

        if current.left is not None:
            queue.append(current.left)         # enqueue children so they're visited after
                                                 # all of the current level is done
        if current.right is not None:
            queue.append(current.right)

    return result

print(level_order(root))

Tracing this on the example tree: queue starts as [1]. Dequeue 1, visit it, enqueue its children -> queue is [2, 3]. Dequeue 2, visit it, enqueue its children -> queue is [3, 4, 5]. Dequeue 3, visit it, enqueue its only child -> queue is [4, 5, 6]. Then 4, 5, 6 are dequeued and visited in turn with nothing left to enqueue.

Output on the example tree: [1, 2, 3, 4, 5, 6]

Time complexity: O(n) — every node is enqueued and dequeued exactly once, each in O(1) thanks to deque. Space complexity: O(w) — the queue holds at most one full level's worth of nodes at a time, where w is the tree's maximum width (in the worst case, a complete tree's bottom level, w = O(n)).

All Four Outputs, Side By Side