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

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

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
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(6);

Inorder Traversal (Left, Node, Right)

import java.util.ArrayList;
import java.util.List;

public static void inorder(TreeNode node, List<Integer> result) {
    if (node == null) {
        return;                       // base case
    }
    inorder(node.left, result);      // visit left subtree first
    result.add(node.val);            // then this node
    inorder(node.right, result);     // then right subtree
}

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)

public static void preorder(TreeNode node, List<Integer> result) {
    if (node == null) {
        return;
    }
    result.add(node.val);            // visit this node first
    preorder(node.left, result);
    preorder(node.right, result);
}

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)

public static void postorder(TreeNode node, List<Integer> result) {
    if (node == null) {
        return;
    }
    postorder(node.left, result);
    postorder(node.right, result);
    result.add(node.val);            // visit this node last
}

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 a Queue)

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.

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.ArrayList;

public static List<Integer> levelOrder(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);                       // enqueue the root first

    while (!queue.isEmpty()) {
        TreeNode current = queue.poll();     // dequeue the next node to visit
        result.add(current.val);

        if (current.left != null) {
            queue.offer(current.left);       // enqueue children so they're visited after
                                                 all of the current level is done
        }
        if (current.right != null) {
            queue.offer(current.right);
        }
    }
    return result;
}

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. 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