Trees, BFS & DFS

Your file explorer, the DOM your React code renders into, the JSON every API returns, the index your database searches — all trees. And every tree question ever asked, in interviews or in production, reduces to one decision: walk it level by level (BFS) or deep first (DFS). Learn those two walks and you’ve learned how to traverse anything.

The Goal

By the end of this module you can:

• Explain what a tree is and point at four you used today without noticing
• Implement a TreeNode and both walks in Java: recursive DFS and queue-based BFS
• Recognize from problem wording which walk a problem wants, in under 30 seconds
• Explain the BST property, why search is O(log n), and how it rots to O(n) when unbalanced
• Solve tree problems recursively by trusting the function on the subtree — no trace-the-whole-call-stack panic

The Lesson

Trees are nested decisions

A tree is nodes with children, no loops, one root. You live inside them:

flowchart TD
    R["project folder"] --> S["src"]
    R --> D["docs"]
    S --> M["Main.java"]
    S --> U["utils"]
    U --> H["Helper.java"]
    D --> RD["readme.md"]

Your file system is a tree. A company org chart is a tree. The browser DOM is a tree of elements inside elements. A JSON response is a tree of objects inside objects. Notice what they share: containment — each node fully owns everything under it. That ownership is why recursion fits trees so naturally: whatever is true of a tree is true of each subtree, just smaller.

Vocabulary you need, no more: root (the top), leaf (no children), depth (how far from the root), binary tree (each node has at most two children, left and right).

TreeNode in Java

Same move as ListNode, with two arrows instead of one:

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

    TreeNode(int val) {
        this.val = val;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(15);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(8);
        System.out.println("root: " + root.val + ", left child: " + root.left.val);
    }
}

Heap objects pointing at heap objects — the exact picture from how Java runs and the previous module. A tree node is a list node that learned to point at two things.

The ONLY two ways to walk anything

This is the whole module in one table. Every traversal of every structure — trees, graphs, mazes, your file system — is one of these two:

Why the signals work: BFS visits everything at distance 1, then distance 2, then 3 — so the first time BFS touches a target, it got there by a shortest route. That’s why “minimum” and “nearest” scream BFS. DFS commits to one branch until it bottoms out — so questions about a complete path or a property of a whole subtree scream DFS.

Recursive DFS — the template

static void dfs(TreeNode node) {
    if (node == null) return;        // the base case - ALWAYS first line
    // preorder: process node HERE - before children
    dfs(node.left);
    // inorder: process node HERE - between children
    dfs(node.right);
    // postorder: process node HERE - after children
}

One skeleton, three traversals — the only difference is where you do the work:

Postorder is your file explorer computing folder sizes: a folder’s size is only known after every child reports in.

Iterative BFS — the template

No recursion here; BFS runs on an explicit queue. Use ArrayDeque — Java’s fast double-ended queue (skip LinkedList, and Stack the class is legacy — ArrayDeque does both jobs):

import java.util.ArrayDeque;

static void bfs(TreeNode root) {
    if (root == null) return;
    ArrayDeque<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        int levelSize = queue.size();            // freeze this level's count
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();        // take from the front
            System.out.print(node.val + " ");
            if (node.left != null) queue.add(node.left);    // children join the back
            if (node.right != null) queue.add(node.right);
        }
        System.out.println("  <- one level done");
    }
}

The levelSize trick is the part interviews test: snapshot the queue size before the inner loop, and exactly one level passes through per outer iteration. Without it you still visit everything in BFS order, but you can’t answer “what’s on level 3” or “average per level”.

One mechanical fact worth saying out loud: swap the queue for a stack in that code and the same loop becomes DFS. The container IS the traversal. (Swap in a priority queue — always serve the smallest — and you get the third great visit order; that’s heaps and greedy, the next module.)

The BST property — and how it rots

A binary search tree adds one rule: everything in left is smaller than the node, everything in right is bigger. That rule turns search into a guided walk:

static boolean search(TreeNode node, int target) {
    if (node == null) return false;
    if (node.val == target) return true;
    return target < node.val ? search(node.left, target)
                             : search(node.right, target);
}

Each comparison discards half the remaining tree — the same halving as binary search, O(log n). A million nodes, ~20 comparisons.

But that promise only holds if the tree is balanced. Insert the values 1, 2, 3, 4, 5 in order into a naive BST and every node goes right: you’ve built a linked list wearing a tree costume, and search is O(n). This is why production trees are self-balancing — Java’s TreeMap and TreeSet use a red-black tree, which does small rotations on insert to keep height O(log n), guaranteed, no matter what order data arrives. You will never implement one; you should be able to say that paragraph in an interview.

Recursion on trees = trust the subtree

The mental unlock that makes tree problems easy. Take maxDepth:

static int maxDepth(TreeNode node) {
    if (node == null) return 0;                  // empty tree has depth 0
    int left = maxDepth(node.left);              // TRUST: the depth of the left subtree
    int right = maxDepth(node.right);            // TRUST: the depth of the right subtree
    return 1 + Math.max(left, right);            // my depth = 1 + my taller child
}

Beginners try to trace every recursive call and drown. Don’t trace — trust. Assume maxDepth(node.left) already returns the correct answer for that smaller tree (it does — same function, smaller input, and the null base case anchors the bottom). Your only job is one node’s worth of logic: given correct answers for my children, what’s my answer? That one-node-at-a-time framing solves the majority of tree interview questions. The deep dive on why this works is the recursion and backtracking module.

Classic traps

The complexity story: both walks visit every node once — O(n) time. Space differs: BFS holds the widest level (up to n/2 nodes on the bottom of a full tree), DFS holds one path (O(height), which is O(log n) balanced, O(n) degenerate).

See It Move

Same tree, three walks. Watch the queue/stack panel — the data structure’s order, not the tree, decides who gets visited next.

Step through it and notice:

• In BFS mode, children join the back of the queue, so an entire level drains before the next begins
• In DFS preorder, each node is visited the moment it’s reached — the stack dives down a branch before touching its sibling
• In DFS inorder on this tree, read out the visit order — smaller values first; on a BST inorder always comes out sorted
• Pick any moment mid-walk and predict the next node from the panel alone, then step to check — that prediction is the skill

Spot The Pattern

Where It Runs In Real Life

File system traversal. find, “search in folder”, disk-usage analyzers, and every recursive delete are tree walks over directories. Folder size is literally postorder DFS: sum the children, then report the parent. When your IDE indexes a project, it’s walking this exact tree.

B-tree indexes — how your database finds rows. Every WHERE id = ? on an indexed column walks a B-tree: a BST generalized to hundreds of children per node so each step is one disk page. Millions of rows, three or four hops. This is the single most valuable tree in your career — it comes back in data modeling when you design indexes.

DOM rendering. The browser parses HTML into a tree, then walks it to compute layout and paint. React’s reconciliation diffs two of these trees. Your JS/React background means you’ve been traversing trees all along — document.querySelector is a DFS.

Org-hierarchy and category queries. “Everyone reporting up to this manager”, “all products under Electronics”, “all replies under this comment” — each is a subtree walk. Whether the tree lives in memory or in a SQL table with parent_id, the traversal is BFS or DFS.

Dependency resolution and social graphs. Maven and npm walk your dependency tree to decide install order — postorder again, dependencies before dependents. And “degrees of separation” or “suggest friends of friends” in a social network is BFS from your node — level 1 is friends, level 2 is mutuals, and BFS’s level-by-level guarantee is exactly what “nearest” needs.

Build This

You’re building TreeLab — a BST you grow, walk both ways, and then deliberately degenerate.

1. Create TreeLab.java and type this:

import java.util.ArrayDeque;

public class TreeLab {

    static class Node {
        int val;
        Node left, right;
        Node(int val) { this.val = val; }
    }

    static Node insert(Node node, int val) {
        if (node == null) return new Node(val);
        if (val < node.val) node.left = insert(node.left, val);
        else node.right = insert(node.right, val);
        return node;
    }

    static void inorder(Node node) {
        if (node == null) return;
        inorder(node.left);
        System.out.print(node.val + " ");
        inorder(node.right);
    }

    static void bfs(Node root) {
        if (root == null) return;
        ArrayDeque<Node> queue = new ArrayDeque<>();
        queue.add(root);
        int level = 0;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            System.out.print("level " + level++ + ": ");
            for (int i = 0; i < levelSize; i++) {
                Node n = queue.poll();
                System.out.print(n.val + " ");
                if (n.left != null) queue.add(n.left);
                if (n.right != null) queue.add(n.right);
            }
            System.out.println();
        }
    }

    static int maxDepth(Node node) {
        if (node == null) return 0;
        return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
    }

    public static void main(String[] args) {
        int[] vals = {50, 30, 70, 20, 40, 60, 80};
        Node root = null;
        for (int v : vals) root = insert(root, v);

        System.out.print("inorder: ");
        inorder(root);
        System.out.println();
        bfs(root);
        System.out.println("depth: " + maxDepth(root));
    }
}

2. Compile and run. The inorder line prints 20 30 40 50 60 70 80 — sorted, even though you inserted in a jumbled order. That’s the BST property plus inorder, live. The BFS lines show three clean levels; depth is 3.

3. Break it — degenerate the BST. Change vals to {10, 20, 30, 40, 50, 60, 70} (already sorted). Run again. Inorder still prints sorted — but look at the BFS output: seven levels, one node each. Depth is 7. You built the linked-list-in-a-costume; search just became O(n). Now say the TreeMap red-black paragraph from the lesson out loud — this is the problem it exists to prevent.

4. Break it — recurse to death. Make vals an array of the numbers 1 to 100000 in order (build it with a for loop). Run. StackOverflowError — each insert recurses one level deeper down the all-right spine, and 100k stack frames is past the JVM’s limit. A balanced tree of the same values would be ~17 deep. Read the trace: it’s the same insert line repeating — your first recursive stack trace.

5. Extend it. Add minDepth using BFS that returns early at the first node with no children, and search(Node node, int target) from the lesson with a counter that prints how many comparisons it made. Compare the count on the balanced tree vs the degenerate one for the same target. That printed number is the whole O(log n) vs O(n) story.

Problems To Solve

The rule: solve until you can write both templates from memory; if stuck 25 min, read the approach, close it, re-solve from scratch.

Check Yourself

1. BFS and DFS each run on which data structure, and what visit order does each produce?
2. The problem says “minimum depth”. Which walk, and why is the other one wasteful?
3. What does inorder traversal give you on a BST, and which interview problems does that one fact unlock?
4. Why is levelSize snapshotted before the inner BFS loop?
5. BST search is O(log n) — what’s the catch, and how do TreeMap and TreeSet dodge it?
6. In maxDepth, what exactly are you trusting when you call maxDepth(node.left)?
7. When does postorder beat preorder? Give a real-system example.
8. Space complexity: what does BFS hold at peak, and what does DFS hold?

Explain it out loud: Draw a seven-node tree on paper. Walk it three times — BFS, preorder, inorder — writing the visit order under each, while narrating what’s in the queue or on the stack at every step. Then explain to the empty chair why “shortest” means BFS and “all paths” means DFS. Stall anywhere = re-run the visualizer in that mode.

Still Unclear?

Copy-paste any of these into Claude — they deepen understanding, they don’t solve for you:

I'm learning tree traversal in Java. Draw a 7 node binary tree in ASCII, then ask
me to list the BFS, preorder, and inorder visit orders myself. Check each, and
where I go wrong, show me the queue or stack contents at the exact step I derailed.

Quiz me on BFS vs DFS recognition: give me 10 one-line tree problem descriptions
one at a time. I answer BFS or DFS and say which signal word tipped me off. Tell
me my score and which signals I keep missing. No code.

I understand maxDepth works but recursion still feels like magic. Without code,
explain why trusting the recursive call is mathematically safe - walk me through
how the null base case anchors it, using induction in plain words for a beginner.

Why AI Can’t Do This For You

AI writes a perfect level-order traversal instantly. But the ticket on your desk never says “do BFS” — it says “category pages load slow when the tree is deep” or “notification fan-out reaches people twice.” Seeing the tree inside the vague sentence, and knowing in 30 seconds whether it’s a level problem or a path problem, is the recognition skill this module drills — and recognition can’t be prompted, because forming the prompt already requires it.

In the interview it’s sharper: you’ll be asked WHY fast — why BFS for minimum depth, why inorder comes out sorted, why the BST guarantee dies unbalanced. Reciting a memorized traversal collapses under one follow-up question. The trust-the-subtree habit and the two-walks instinct only get built the way you just built them: by hand, broken on purpose, explained to an empty chair.

Module done? Add it to today’s tracker