Tree Traversals

Visit every node exactly once — and pick the order that already answers the question.

intermediate~75 min6 simulations9 problems

▶ guided lesson ⚡ 1-minute summary ↻ 14 recall cards

before this: Recursion · Stacks · Queues

Section

01 · why it exists

Why this exists, and the weight it carries

since1857

Binary tree

Arthur Cayley (the name "tree"); no single inventor of the linked binary tree in programs

In 1857 the mathematician Arthur Cayley published "On the theory of the analytical forms called trees" in the Philosophical Magazine. He was counting rooted, branching shapes while studying how calculus operators combine — and the name tree stuck. In programs, a node holding two links (left, right) became a standard building block of early list-processing and compilers; no one person is credited with it. Today every node in a Java TreeMap is built on it: a key and a value, left and right child references (plus a parent link and a red/black colour bit).

the problem it solvedRepresenting hierarchy and branching — anything where one thing splits into at most two smaller things of the same kind.

its jobs today

Java collections: TreeMap and TreeSet are red-black trees — binary search trees that rebalance themselves.
Compilers: javac turns a + b * c into a syntax tree whose operator nodes have two children.
Compression: Huffman coding builds a binary tree where left = 0 and right = 1; the path to a leaf is that character's code.

the weight it carries

Illustrative: 10 lakh (10⁶) keys. Kept in a balanced binary tree, the root-to-leaf path is about ⌈log₂ 10⁶⌉ = 20 nodes, so any lookup touches ~20 nodes instead of scanning up to 10⁶. The same keys in a skewed tree make that path 10⁶ long.

without it

Hierarchies would be flattened into lists: every "find", "insert in order" or "evaluate this expression" becomes a linear scan.

when · why · how

when: Data that branches (expressions, decisions, sorted keys, folder-like structures) or must stay ordered while it changes.
why: A balanced tree keeps every path O(log n) long; the price is pointer-chasing (two references per node) and the risk of an O(n) skewed shape if nothing rebalances it.
how: class TreeNode { int val; TreeNode left, right; } on LeetCode; TreeMap<K, V> when you need a balanced ordered tree in real code.

since1960–1979

Depth-first traversal (pre, in, post order)

Alan Perlis & Charles Thornton; Donald Knuth; Joseph M. Morris

In 1960 Perlis and Thornton's "threaded lists" reused empty links to point back up a structure — Knuth later credited them with the threaded tree. Knuth's Fundamental Algorithms (1968), §2.3.1 "Traversing Binary Trees", set out the three depth-first orders and how to walk a tree with an explicit stack instead of recursion. It also posed a challenge: inorder with no stack and no recursion, leaving the tree unchanged. In 1979 Joseph M. Morris gave the best-known answer: thread the tree temporarily, walk it in O(1) extra space, and restore it before finishing.

the problem it solvedVisiting every node exactly once in a predictable order — with recursion, with an explicit stack, or (Morris) with almost no memory.

its jobs today

Browsers: querySelectorAll returns elements in document order — a preorder walk of the DOM tree.
Compilers: bytecode for an expression is emitted in postorder — operands first, then the operator — because the JVM is a stack machine.
Sorted iteration: walking a TreeMap in key order is an inorder traversal.

the weight it carries

Illustrative: a balanced tree of 10⁶ nodes. A DFS keeps at most ~20 nodes on its stack at once (one per level) while visiting all 10⁶. The same walk over a 10⁶-node chain needs 10⁶ stack entries — fine in an ArrayDeque on the heap, a StackOverflowError as recursion.

without it

There'd be no systematic way to copy, print, compare or free a tree — each task would invent its own ad-hoc walk and miss nodes.

when · why · how

when: You must visit everything and the order matters: preorder to copy or serialize, inorder for sorted output, postorder when parents need their children's results.
why: O(n) time and O(h) space. Recursion is shortest to write; an explicit stack survives deep trees; Morris gets O(1) space by temporarily modifying the tree.
how: Recursion: move one out.add line to switch orders. Iterative: Deque<TreeNode> stack = new ArrayDeque<>() with push / pop.

since1945–1961

Breadth-first traversal (level order)

Konrad Zuse; Edward F. Moore; C. Y. Lee

The idea is usually traced to Konrad Zuse, whose 1945 manuscript on the Plankalkül language used it to find the connected parts of a graph — it was published only in 1972. Edward F. Moore reinvented it (presented in 1957, printed in 1959) to find the shortest path through a maze: explore everything 1 step away, then 2 steps, and so on. In 1961 C. Y. Lee turned it into a path-finding algorithm for wiring diagrams. Level-order traversal is exactly this search, run on a tree from the root.

the problem it solvedVisiting things in order of distance from a start — so the first time you reach something, you reached it by the fewest steps.

its jobs today

Shortest paths when every step costs the same: game maps, grids, friend-of-a-friend suggestions (all in the Graphs chapter).
Level-wise work on trees: printing an org chart or a folder tree level by level, or finding the shallowest match.

the weight it carries

Illustrative: a perfect tree of 2²⁰ − 1 ≈ 10⁶ nodes. BFS reaches a node at depth 3 after at most 1 + 2 + 4 + 8 = 15 polls, while a DFS could first walk the root's entire other subtree — 2¹⁹ − 1 = 524,287 nodes. The cost: at the last level the queue holds 2¹⁹ = 524,288 nodes at once.

without it

"Nearest" questions would need a full search plus a comparison of every candidate, instead of stopping at the first hit.

when · why · how

when: The question is about levels, rows or the nearest / shallowest something — or distances where every edge counts as 1.
why: O(n) time; O(w) memory for the widest level. It finds the shallowest answer first, but a wide tree costs a lot of queue memory.
how: Deque<TreeNode> queue = new ArrayDeque<>(); offer children, poll the front; read int size = queue.size() before each level.

since?

Serialization with null markers

Writing a tree as a flat sequence with a marker for every missing child is old programming folklore; we found no single inventor to credit.

its jobs today

Data formats: JSON, HTML and XML are trees written as text — every opening bracket or tag is a node written before its children.
Saving and sending objects: a tree in memory becomes a string or byte stream for a file, a cache or a network call, and is rebuilt on the other side.
LeetCode's tree notation itself, like [1,null,2], is level order with null markers.

the weight it carries

Illustrative: a tree of 10⁴ nodes. Preorder with markers writes 10⁴ values + 10,001 markers ≈ 2·10⁴ tokens, and exactly one tree matches them. Without markers, even 10 values in preorder fit Catalan(10) = 16,796 different shapes — the reader can't know which one you meant.

without it

A tree could not leave the program that built it — no saving to disk, no sending over a network, no caching.

when · why · how

when: A tree must be stored, sent, cached or compared as a string.
why: Markers make a single traversal unambiguous: O(n) to write and O(n) to read, in the same order. Two traversals without markers also work but need unique values.
how: StringBuilder with "#," for null and val + "," otherwise; read back with data.split(",") into an ArrayDeque<String>.

02 · plain english

The idea in 30 seconds

A binary tree is a node with a value and at most two children — and each child is itself a binary tree.

A traversal visits every node once. Depth-first (pre, in, post order) goes deep using a stack; breadth-first (level order) goes level by level using a queue.

Many tree problems are just the right visiting order plus one line of work at each visit.

picture this

Your File Explorer folder tree, walked two ways. Depth-first: open Projects and everything inside it before you touch Downloads — that's how the Windows tree command prints folders (preorder). Breadth-first: list every top-level folder, then every folder one level down — so the first match you find is the shallowest one.

03 · remember

What you must know

Terminology: root (top, no parent), leaf (no children), edge (parent→child link). Depth = edges from the root down to a node. Height = edges on the longest path from a node down to a leaf. A tree's height is its root's height.
Shapes: full = every node has 0 or 2 children. Complete = every level full except maybe the last, filled left to right (heaps). Perfect = all levels full (2^(h+1) − 1 nodes). Balanced = at every node the two subtree heights differ by at most 1, so h = O(log n).
*DFS orders differ only in when you touch the node:* preorder = before the children (copy, serialize), inorder = between them (sorted order in a BST), postorder = after them (heights, sizes, deleting).
Iterative DFS: an ArrayDeque does the call stack's job. Inorder loop: dive left pushing every node, pop one, visit it, go right. Postorder trick: a root → right → left preorder, reversed.
BFS uses a queue. Snapshot size = queue.size() at the start of each round to process exactly one level — the trick behind every "level" problem.
Space: DFS holds one root-to-node path → O(h). BFS holds about one level → O(w), the widest level. A perfect tree is short and wide (DFS wins); a skewed chain is tall and thin (BFS wins).
*When the order is the answer:* level lists, zigzag, right side view, averages, next pointers and serialization are all "traverse in the right order, do one line of work per node".
A tree is a graph that only points down. Record each node's parent in a HashMap and you can walk up too — then a BFS from any node measures distances (All Nodes Distance K).

04 · see it

Play with it in 3D

Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.

sim

Preorder · inorder · postorder walk

Type pre, in or post. The call stack (right) is the path from the root to the current node; the output fills in when the node is *visited*.

loading simulation…

javajava.util.*

1class RecursiveDfs {2    /** Root, then left subtree, then right subtree. */3    static void preorder(TreeNode node, List<Integer> out) {4        if (node == null) return;5        out.add(node.val);                 // visit BEFORE the children6        preorder(node.left, out);7        preorder(node.right, out);8    }9 10    /** Left subtree, then root, then right subtree. */11    static void inorder(TreeNode node, List<Integer> out) {12        if (node == null) return;13        inorder(node.left, out);14        out.add(node.val);                 // visit BETWEEN the children15        inorder(node.right, out);16    }17 18    /** Left subtree, then right subtree, then root. */19    static void postorder(TreeNode node, List<Integer> out) {20        if (node == null) return;21        postorder(node.left, out);22        postorder(node.right, out);23        out.add(node.val);                 // visit AFTER the children24    }25}

sim

Inorder without recursion

An explicit stack does exactly what the call stack did: remember the nodes we still have to come back to.

loading simulation…

javajava.util.*

1class IterativeDfs {2    static List<Integer> preorder(TreeNode root) {3        List<Integer> out = new ArrayList<>();4        if (root == null) return out;5        Deque<TreeNode> stack = new ArrayDeque<>();6        stack.push(root);7        while (!stack.isEmpty()) {8            TreeNode node = stack.pop();9            out.add(node.val);10            // push right first so left is popped (visited) first11            if (node.right != null) stack.push(node.right);12            if (node.left != null) stack.push(node.left);13        }14        return out;15    }16 17    static List<Integer> inorder(TreeNode root) {18        List<Integer> out = new ArrayList<>();19        Deque<TreeNode> stack = new ArrayDeque<>();20        TreeNode cur = root;21        while (cur != null || !stack.isEmpty()) {22            while (cur != null) {                    // dive as far left as possible23                stack.push(cur);24                cur = cur.left;25            }26            cur = stack.pop();                       // leftmost unvisited node27            out.add(cur.val);28            cur = cur.right;                         // then its right subtree29        }30        return out;31    }32 33    /** Postorder = reverse of a "root, right, left" preorder. */34    static List<Integer> postorder(TreeNode root) {35        List<Integer> out = new ArrayList<>();36        if (root == null) return out;37        Deque<TreeNode> stack = new ArrayDeque<>();38        stack.push(root);39        while (!stack.isEmpty()) {40            TreeNode node = stack.pop();41            out.add(node.val);42            if (node.left != null) stack.push(node.left);43            if (node.right != null) stack.push(node.right);44        }45        Collections.reverse(out);46        return out;47    }48}

sim

Level-order BFS with a queue

Amber nodes are waiting in the queue. `size` freezes the current level so the next level never mixes in.

loading simulation…

javajava.util.*

1class Solution {2    public List<List<Integer>> levelOrder(TreeNode root) {3        List<List<Integer>> levels = new ArrayList<>();4        if (root == null) return levels;5        Deque<TreeNode> queue = new ArrayDeque<>();6        queue.offer(root);7        while (!queue.isEmpty()) {8            int size = queue.size();                         // nodes on THIS level9            List<Integer> level = new ArrayList<>(size);10            for (int i = 0; i < size; i++) {11                TreeNode node = queue.poll();12                level.add(node.val);13                if (node.left != null) queue.offer(node.left);14                if (node.right != null) queue.offer(node.right);15            }16            levels.add(level);17        }18        return levels;19    }20}

sim

Right side view — the last node of each level

Same BFS, one extra line: the node polled at i = size − 1 is the one you see from the right, even when it lives in the left subtree.

loading simulation…

javajava.util.*

1class Solution {2    public List<Integer> rightSideView(TreeNode root) {3        List<Integer> view = new ArrayList<>();4        if (root == null) return view;5        Deque<TreeNode> queue = new ArrayDeque<>();6        queue.offer(root);7        while (!queue.isEmpty()) {8            int size = queue.size();                             // nodes on THIS level9            for (int i = 0; i < size; i++) {10                TreeNode node = queue.poll();11                if (i == size - 1) view.add(node.val);           // last of the level = visible12                if (node.left != null) queue.offer(node.left);13                if (node.right != null) queue.offer(node.right);14            }15        }16        return view;17    }18}

sim

Serialize and deserialize with null markers

Preorder writes every node and every null (#). The reader consumes the tokens in the same order, so each subtree rebuilds itself.

loading simulation…

javajava.util.*

1class Codec {2    /** Preorder, "#" for null: "1,2,#,#,3,4,#,#,5,#,#". */3    public String serialize(TreeNode root) {4        StringBuilder sb = new StringBuilder();5        write(root, sb);6        return sb.toString();7    }8 9    private void write(TreeNode node, StringBuilder sb) {10        if (node == null) { sb.append("#,"); return; }11        sb.append(node.val).append(',');12        write(node.left, sb);13        write(node.right, sb);14    }15 16    public TreeNode deserialize(String data) {17        Deque<String> tokens = new ArrayDeque<>(Arrays.asList(data.split(",")));18        return read(tokens);19    }20 21    /** Consumes exactly one subtree's worth of tokens, in the same order they were written. */22    private TreeNode read(Deque<String> tokens) {23        String token = tokens.poll();24        if (token.equals("#")) return null;25        TreeNode node = new TreeNode(Integer.parseInt(token));26        node.left = read(tokens);27        node.right = read(tokens);28        return node;29    }30}

sim

All nodes distance K — walk up, not just down

Step 1 records every parent. Step 2 is a BFS from the target over left, right and parent links; after k rounds the queue is the answer.

loading simulation…

javajava.util.*

1class Solution {2    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {3        Map<TreeNode, TreeNode> parent = new HashMap<>();4        linkParents(root, null, parent);                       // now every node can also go UP5        Deque<TreeNode> queue = new ArrayDeque<>();6        Set<TreeNode> seen = new HashSet<>();7        queue.offer(target);8        seen.add(target);9        for (int dist = 0; dist < k && !queue.isEmpty(); dist++) {   // one ring per round10            for (int size = queue.size(); size > 0; size--) {11                TreeNode node = queue.poll();12                for (TreeNode next : new TreeNode[] {node.left, node.right, parent.get(node)}) {13                    if (next != null && seen.add(next)) queue.offer(next);14                }15            }16        }17        List<Integer> answer = new ArrayList<>();18        for (TreeNode node : queue) answer.add(node.val);      // the queue now holds ring k19        return answer;20    }21 22    private void linkParents(TreeNode node, TreeNode par, Map<TreeNode, TreeNode> parent) {23        if (node == null) return;24        parent.put(node, par);25        linkParents(node.left, node, parent);26        linkParents(node.right, node, parent);27    }28}

05 · cost

Time & space, explained

Traversals (n nodes, height h, widest level w)
	Time	Extra space	why
DFS (pre/in/post), recursive	O(n)	O(h)	Each node is entered once; the call stack only holds the current root-to-node path.
DFS with an explicit ArrayDeque stack	O(n)	O(h)	Each node is pushed and popped once; same path on the stack — but on the heap, so deep trees don't overflow.
Morris inorder (threads)	O(n)	O(1)	Temporarily points empty right links back to ancestors, then removes them; each edge is walked a constant number of times.
BFS level order with a queue	O(n)	O(w)	Each node is offered and polled once; the queue holds about one level (up to ~n/2 in a perfect tree).
Serialize / deserialize (preorder + markers)	O(n)	O(n)	n values and n + 1 null markers are written once and read once; the string itself is O(n).
Parent map + BFS from a node	O(n)	O(n)	One DFS fills the map; the BFS offers each node at most once thanks to the seen set.

Stack vs queue memory at the extremes (n ≈ 10⁶)
	DFS stack (h)	BFS queue (w)	why
Perfect tree, n = 2²⁰ − 1 = 1,048,575	20 frames	524,288 nodes	20 levels deep, but the last level alone holds 2¹⁹ nodes — half the tree waits in the queue at once.
Skewed chain, n = 10⁶	10⁶ frames → StackOverflowError	1 node	The tree is a linked list in disguise: recursion depth equals n, while each level has one node.

06 · java

Raw vs Collections Framework

The TreeNode class

javaTreeNode (same shape LeetCode gives you)java.util.*

1/** One node of a binary tree: a value plus links to at most two children. */2class TreeNode {3    int val;4    TreeNode left;   // null when there is no left child5    TreeNode right;  // null when there is no right child6 7    TreeNode(int val) {8        this.val = val;9    }10 11    TreeNode(int val, TreeNode left, TreeNode right) {12        this.val = val;13        this.left = left;14        this.right = right;15    }16}

A tree is just nodes holding references. null means "no child here" — every leaf has two nulls.
On LeetCode, TreeNode is predefined; you never write it. In real code you would make the fields private or use a record for immutable trees.
n nodes always have exactly n − 1 edges (every node except the root has one parent) and n + 1 null child slots.

Depth-first: recursion vs an explicit stack

javarecursivejava.util.*

1class RecursiveDfs {2    /** Root, then left subtree, then right subtree. */3    static void preorder(TreeNode node, List<Integer> out) {4        if (node == null) return;5        out.add(node.val);                 // visit BEFORE the children6        preorder(node.left, out);7        preorder(node.right, out);8    }9 10    /** Left subtree, then root, then right subtree. */11    static void inorder(TreeNode node, List<Integer> out) {12        if (node == null) return;13        inorder(node.left, out);14        out.add(node.val);                 // visit BETWEEN the children15        inorder(node.right, out);16    }17 18    /** Left subtree, then right subtree, then root. */19    static void postorder(TreeNode node, List<Integer> out) {20        if (node == null) return;21        postorder(node.left, out);22        postorder(node.right, out);23        out.add(node.val);                 // visit AFTER the children24    }25}

javaiterative with ArrayDequejava.util.*

1class IterativeDfs {2    static List<Integer> preorder(TreeNode root) {3        List<Integer> out = new ArrayList<>();4        if (root == null) return out;5        Deque<TreeNode> stack = new ArrayDeque<>();6        stack.push(root);7        while (!stack.isEmpty()) {8            TreeNode node = stack.pop();9            out.add(node.val);10            // push right first so left is popped (visited) first11            if (node.right != null) stack.push(node.right);12            if (node.left != null) stack.push(node.left);13        }14        return out;15    }16 17    static List<Integer> inorder(TreeNode root) {18        List<Integer> out = new ArrayList<>();19        Deque<TreeNode> stack = new ArrayDeque<>();20        TreeNode cur = root;21        while (cur != null || !stack.isEmpty()) {22            while (cur != null) {                    // dive as far left as possible23                stack.push(cur);24                cur = cur.left;25            }26            cur = stack.pop();                       // leftmost unvisited node27            out.add(cur.val);28            cur = cur.right;                         // then its right subtree29        }30        return out;31    }32 33    /** Postorder = reverse of a "root, right, left" preorder. */34    static List<Integer> postorder(TreeNode root) {35        List<Integer> out = new ArrayList<>();36        if (root == null) return out;37        Deque<TreeNode> stack = new ArrayDeque<>();38        stack.push(root);39        while (!stack.isEmpty()) {40            TreeNode node = stack.pop();41            out.add(node.val);42            if (node.left != null) stack.push(node.left);43            if (node.right != null) stack.push(node.right);44        }45        Collections.reverse(out);46        return out;47    }48}

The three recursive versions are identical except for where out.add sits. Learn one, move one line, get the others.
Iterative preorder pushes the right child first so the left one is on top and comes out first.
Iterative inorder: dive left pushing everything, pop one, visit it, then go right. Bas itna yaad rakho — BST problems reuse this exact loop (kth smallest, BST iterator).
Iterative postorder trick: a root → right → left preorder, reversed, is left → right → root.
Use ArrayDeque as the stack, never java.util.Stack: Stack extends the synchronized Vector and is slower and considered legacy.

Breadth-first: the queue

javaBFS with ArrayDequejava.util.*

1class Bfs {2    /** Visits nodes level by level, left to right. */3    static List<Integer> levelOrder(TreeNode root) {4        List<Integer> out = new ArrayList<>();5        if (root == null) return out;          // ArrayDeque rejects null6        Deque<TreeNode> queue = new ArrayDeque<>();7        queue.offer(root);8        while (!queue.isEmpty()) {9            TreeNode node = queue.poll();      // oldest discovered node first10            out.add(node.val);11            if (node.left != null) queue.offer(node.left);12            if (node.right != null) queue.offer(node.right);13        }14        return out;15    }16}

offer adds at the rear, poll removes from the front — first discovered, first processed. That is why BFS goes level by level.
ArrayDeque throws NullPointerException on null elements. Check children before offering them.
Need levels separately? Read queue.size() into a variable before the inner loop (see Level Order Traversal).

When nulls are data: LinkedList as the queue

javaBFS codec with LinkedListjava.util.*

1class Codec {2    /** Level order, "#" for a missing child: "1,2,3,#,#,4,5,#,#,#,#". */3    public String serialize(TreeNode root) {4        if (root == null) return "";5        StringBuilder sb = new StringBuilder();6        Queue<TreeNode> queue = new LinkedList<>();   // LinkedList allows null; ArrayDeque does not7        queue.offer(root);8        while (!queue.isEmpty()) {9            TreeNode node = queue.poll();10            if (node == null) { sb.append("#,"); continue; }11            sb.append(node.val).append(',');12            queue.offer(node.left);13            queue.offer(node.right);14        }15        return sb.toString();16    }17 18    public TreeNode deserialize(String data) {19        if (data.isEmpty()) return null;20        String[] tokens = data.split(",");21        TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));22        Deque<TreeNode> parents = new ArrayDeque<>();23        parents.offer(root);24        int i = 1;25        while (!parents.isEmpty()) {          // tokens come in pairs: left child, right child26            TreeNode parent = parents.poll();27            if (!tokens[i].equals("#")) {28                parent.left = new TreeNode(Integer.parseInt(tokens[i]));29                parents.offer(parent.left);30            }31            i++;32            if (!tokens[i].equals("#")) {33                parent.right = new TreeNode(Integer.parseInt(tokens[i]));34                parents.offer(parent.right);35            }36            i++;37        }38        return root;39    }40}

Serialization must record the missing children, so the queue has to hold null. LinkedList allows it; ArrayDeque does not.
Build strings with StringBuilder.append — += in a loop copies the whole string every time (O(n²)).
data.split(",") drops trailing empty strings, so a trailing comma is harmless.

Java API you will actually use
call	does	cost
`Deque<TreeNode> st = new ArrayDeque<>()`	Stack for iterative DFS (`push` / `pop` / `peek` work on the head)	O(1) amortized
`queue.offer(x) / queue.poll()`	Enqueue at the rear / dequeue from the front (BFS)	O(1) amortized / O(1)
`queue.size() / isEmpty()`	Snapshot one level's width; loop condition	O(1)
`new LinkedList<>() (as a Queue)`	A queue that accepts `null` — needed only when nulls are data	O(1) per offer/poll
`level.addFirst(x) / addLast(x) on a Deque`	Build a zigzag level from either end	O(1)
`Collections.reverse(list)`	Turns root-right-left into postorder; reverses a level	O(n)
`Map<TreeNode, TreeNode> parent = new HashMap<>()`	Parent links, so you can walk up the tree	O(1) average
`Set<TreeNode> seen; seen.add(x)`	`add` returns false if x was already there — one call checks and marks	O(1) average
`sb.append(x) / s.split(",")`	Write / read a serialized tree	O(1) amortized / O(length)

Copy, print or serialize a tree top-down

→ Preorder DFS

The root comes first, so a reader can rebuild it in the same order.

Visit a BST in sorted order

→ Inorder DFS

Left (smaller) → node → right (larger).

A node's answer needs its children's answers

→ Postorder (see Tree Recursion)

Children finish before the parent combines their results.

Anything per level: lists, averages, right view, next pointers

→ BFS with a size snapshot

The queue naturally holds one level at a time.

Tree may be very deep (10⁵ skewed nodes)

→ Iterative DFS with ArrayDeque, or BFS

Avoids StackOverflowError: heap memory is far larger than the thread stack.

Queue that must hold null markers

→ LinkedList as Queue

ArrayDeque rejects null.

Distances that can go up through parents

→ HashMap parent links + BFS with a seen set

Turns the tree into an undirected graph; BFS visits nodes in order of distance.

07 · recognise

Spot the pattern

"Level", "row", "zigzag", "right side view", "average of each level"

BFS with size = queue.size() per round

"Can you do it without recursion?"

Explicit ArrayDeque stack — inorder: dive left, pop, visit, go right

Values of a BST in sorted order, k-th smallest

Inorder traversal

"Copy", "serialize", "encode" a tree

Preorder (or BFS) with a marker for every null

"Width", positions, gaps that count

Number nodes like a heap array (2p, 2p + 1); re-base per level

"Distance k from a node", "time to spread through the tree"

Parent map → undirected graph → BFS from the node

"Point each node to its right neighbour"

Level order; for O(1) space walk the level you already linked

"Inorder with O(1) extra space"

Morris traversal (temporary threads, then restore)

08 · traps & tricks

Mistakes to avoid, tricks to use

traps

Offering null children to an ArrayDeque — it throws. Check if (node.left != null) first.
Using queue.size() directly in the for condition: it changes while you offer children. Store it in a variable first.
Iterative preorder pushing the left child before the right — you get root → right → left.
Iterative inorder looping only while (!stack.isEmpty()) — it stops before the last right subtree. The condition is cur != null || !stack.isEmpty().
Right side view by following only .right pointers — misses levels where the rightmost node lives in the left subtree.
Serializing without separators (1, 23 vs 12, 3) or without null markers (different shapes, same string).
Zigzag by swapping the order you offer children — the next level comes out scrambled. Only change where values go in the output list.
Max width without re-basing positions: they double every level and overflow after ~63 levels even in a long.
BFS on a tree-with-parents without a seen set: you walk back the way you came and count nodes twice.

tricks

Before coding, say the order out loud: "I need levels, so BFS" or "I need sorted order, so inorder". Half the problem is choosing it.
Chalo, dry-run karte hain: draw a 5–7 node tree with one gap and one deep branch, and walk your loop by hand. That covers almost every bug.
Edge cases to test every time: empty tree, single node, left-skewed, right-skewed, a level with gaps, negative values.
State space for both extremes: DFS O(h) — O(log n) balanced, O(n) skewed; BFS O(w) — up to n/2 for a perfect tree.
When asked "can you do it without recursion?", reach for ArrayDeque: a stack for DFS, a queue for BFS.
Write the size-snapshot BFS loop from memory until it takes you under a minute — it solves five problems in this chapter.

09 · why & how

Questions you might be too shy to ask

Does "binary tree" mean the values are sorted?

No. "Binary" only describes the shape: each node has at most two children. The values can be in any order, so inorder of a plain binary tree is not sorted. Only a binary search tree (BST) promises left < node < right. Read the problem title carefully — it changes the whole solution.

How do I read LeetCode's tree input like [1,null,2,3]?

It is level order, left to right, with null for a missing child. 1 is the root. Its children are null (left) and 2 (right). The next tokens are 2's children, so 3 is 2's left child. A null gets no child slots of its own, and trailing nulls are dropped.

Height vs depth — which is which?

Depth looks up: how many edges from the root down to this node (root = 0). Height looks down: how many edges from this node to its deepest leaf (leaf = 0). The tree's height = the root's height = the deepest node's depth. LeetCode's "maximum depth" counts nodes, so one node has depth 1 there.

How do I choose between preorder, inorder, postorder and level order?

Ask what you need at each node. Need levels or "nearest"? Level order. Need sorted order from a BST? Inorder. Need to write the tree down so it can be rebuilt? Preorder (root first). Need the children's answers before the node's? Postorder — that's the next chapter, Tree Recursion.

How does the recursion know to come back up to the parent?

Every call gets its own frame on the call stack, holding its own node. When walk(node.left) hits null, it returns — and Java simply continues the parent's frame at the next line. So after the left subtree finishes, the parent runs out.add(node.val) and then walk(node.right). Nothing magic: "come back" just means "the inner call finished". Watch the call-stack panel in the sim.

Why is the base case node == null and not "node is a leaf"?

Checking null covers every case with one line: a leaf calls on two nulls and stops. A leaf-only check breaks on a node with one child — the call on its missing side gets null and crashes with NullPointerException. It also handles the empty tree: root = null returns an empty list straight away. For BFS, add if (root == null) return result; before offer(root), because ArrayDeque rejects null.

Why is DFS space O(h) but BFS space O(w)?

DFS only remembers the path from the root to where it is now — at most h + 1 nodes. BFS remembers the whole frontier: the rest of the current level plus the next one, so its memory follows the widest level w. A perfect tree of about a million nodes (2²⁰ − 1) has h = 19 but w = 524,288 on its last level.

Graphs need a visited set. Why don't tree traversals?

In a tree, links only point down and every node has exactly one parent. So there is only one way to reach each node — you can never arrive twice. The moment you add parent links (All Nodes Distance K), you can walk back up the way you came. Then you need seen, exactly like a graph.

Level problems — do I have to use BFS?

BFS is the natural fit, but DFS works too: pass depth down as a parameter. When depth == result.size(), you are the first node of a new level, so open a new list. Right side view with DFS: visit the right child first and record the first node you see at each depth. Pick BFS when you need to stop at the first (nearest) level; either is fine for collecting all levels.

Why did all my levels come out identical (or empty)?

You probably reused one list: result.add(level); level.clear();. result stores a reference to that same list, so clearing it clears every "saved" level. Create a fresh List<Integer> level = new ArrayList<>() at the start of each round. Simple hai — one new list per level.

Why does inorder traversal matter so much?

On a binary search tree, inorder visits values in sorted order. Validate BST, kth smallest and BST iterator are "just inorder" — usually the iterative loop from this chapter, paused and resumed.

Will recursion overflow the stack in an interview?

Usually not on LeetCode — most test trees are shallow. (People also report that its Java judge has a bigger stack than a default thread, but that is community-reported, not documented.) Still, constraints allow 10⁴–10⁵ nodes, and a fully skewed tree that size can overflow a default Java thread stack — how deep is too deep depends on your setup. Mention the risk and that an iterative ArrayDeque version (or BFS) fixes it — interviewers want to hear that.

Can I rebuild a tree from just one traversal?

Not from plain values — preorder [1, 2] could be 2 as a left or a right child. You need either two traversals (preorder + inorder, see Tree Recursion) or one traversal that also records the nulls, which is exactly what serialization does.

Do interviewers expect Morris traversal?

Rarely as the first answer. It's the follow-up to "inorder in O(1) extra space". Know the idea — thread the rightmost node of the left subtree back to the current node, then remove the thread — and its catch: it modifies the tree while running, so no other code may read the tree during the walk.

10 · practice

Interview problems

Every problem has brute → better → optimal solutions in Java, with complexity and a dry run. show patterns & complexity

#94
Binary Tree Inorder Traversalmust-do
EasyMicrosoftBloombergGoogleAmazonMeta
#102
Binary Tree Level Order Traversalmust-do
MediumBloombergAmazonMicrosoftAppleOracle+1
#637
Average of Levels in Binary Tree
EasyMetaGoogleAmazon
#199
Binary Tree Right Side Viewmust-do
MediumMetaOracleAmazonByteDance / TikTokUber+1
#103
Binary Tree Zigzag Level Order Traversal
MediumAmazonMicrosoftBloombergLinkedInGoogle+1
#117
Populating Next Right Pointers in Each Node II
MediumBloombergMetaMicrosoftAmazonGoogle
#662
Maximum Width of Binary Tree
MediumAmazonBloombergGoogleMicrosoftMeta
#863
All Nodes Distance K in Binary Treemust-do
MediumMetaAmazonMicrosoftGoogleBloomberg
#297
Serialize and Deserialize Binary Treemust-do
HardLinkedInMicrosoftByteDance / TikTokUberAmazon+1

Also practise this here

Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.

#230
Kth Smallest Element in a BST
Mediumin BST
Inorder on a BST is sorted order — stop the iterative inorder loop at the k-th pop.
#173
Binary Search Tree Iterator
Mediumin BST
The iterative inorder loop, paused between calls: the stack keeps the left spine.

11 · revise

The whole chapter on one screen

9 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

what it is
A traversal visits every node once. DFS (pre / in / post) goes deep with a stack; BFS (level order) goes level by level with a queue.
use it when
Levels, rows, "nearest" → BFS. Sorted BST order → inorder. Copy / serialize → preorder. Children before parent → postorder.
template
BFS: offer(root); while (!q.isEmpty()) { int size = q.size(); for (i < size) { poll; offer kids; } }
template
Iterative inorder: while (cur != null || !st.isEmpty()) { while (cur != null) { push; cur = cur.left; } cur = pop(); visit; cur = cur.right; }
cost
All traversals O(n) time. DFS space O(h): 20 frames for a balanced 10⁶-node tree, 10⁶ for a chain. BFS space O(w): up to n/2.
trap
for (int i = 0; i < queue.size(); i++) mixes levels — the queue grows inside the loop. Freeze size first.
trap
ArrayDeque rejects null: check children before offer. Need nulls in the queue (serialization)? Use LinkedList.
pro tip
Distance can go up too? Store parents in a HashMap, then BFS with a seen set — the tree is now an undirected graph.
pro tip
Serialize = preorder + # for every null + a separator. One traversal with markers rebuilds the exact tree.

12 · recall

Flip, remember, repeat

card 1 / 14

recall

Preorder, inorder, postorder: where does the "visit" line go in each?

tap or Space to flip ↻

Question 1: Preorder, inorder, postorder: where does the "visit" line go in each?

13 · check yourself

Quick quiz

Preorder of the tree root 1, left child 2 (with children 4 and 5), right child 3?
What is the extra space of recursive DFS on a tree with n nodes and height h?
In BFS level order, why store `int size = queue.size()` before the inner loop?
Why does `queue.offer(node.left)` sometimes throw with ArrayDeque?
A perfect tree has 2²⁰ − 1 nodes. Roughly how many nodes can a level-order queue hold at once?
Zigzag level order: what should change on odd levels?
Maximum Width numbers nodes like a heap. A node at position 5 has children at…
All Nodes Distance K: why does the BFS need a `seen` set even though a tree has no cycles?

0/0 correct · 8 left

14 · learn more