These are the notes for DSA episode 36, the first episode on trees. A tree stores data where every item can have items "below" it, like a school's chain of command. We define every tree word from zero, write a Node class in Java, and visit every node in the three depth-first orders (preorder, inorder, postorder). Then the interview problem Binary Tree Level Order Traversal (LeetCode 102): the obvious way walks the tree once per level, which is O(n · h) and times out on a tree with ten lakh nodes and 10,000 levels; the fix is breadth-first search with a queue, one level at a time, in O(n). Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.
The problem, in real life
At a school, the principal is at the top and reports to nobody. Two vice principals report to the principal. Each class teacher reports to exactly one vice principal. Store this in an array (principal, VP, VP, teacher, teacher, teacher) and you have lost who reports to whom. We need a shape where every item points to the items directly below it: a tree.
| At school | In a tree |
|---|---|
| A person | a node |
| "reports to" link | an edge |
| The principal | the root (the only node with no parent) |
| A vice principal and their teachers | a parent and its children |
| A class teacher with nobody below | a leaf |
| "How many bosses above you" | depth (edges from the root) |
| Everyone with the same depth | a level |
| Passing an announcement down, level by level | level order traversal |
Tree words, from zero
- Node: one item in the tree. Edge: the link from a parent to a child.
- Root: the top node. Trees are drawn upside down: root at the top.
- Parent / child: a node and a node directly below it. Every node except the root has exactly one parent.
- Leaf: a node with no children.
- Depth of a node: number of edges from the root (the root has depth 0). Level d: all nodes at depth d.
- Height of a tree: the number of levels (in these notes: an empty tree has height 0, one node has height 1).
- Binary tree: every node has at most two children, called left and right.
Our example tree (used everywhere below):
1
/ \
2 3
/ \ \
4 5 6
Root 1; 2 and 3 are its children; 4, 5, 6 are leaves; 3 has only a right child. Depth 0: 1; depth 1: 2 3; depth 2: 4 5 6. Height 3.
A Node class in Java
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
left and right are references to other nodes; null means "no child here". Building the example tree:
Node t = new Node(1, new Node(2, new Node(4), new Node(5)),
new Node(3, null, new Node(6)));
Depth-first traversals: three orders
A traversal visits every node once. Depth-first means: go all the way down one branch before the next, which recursion does naturally. The three orders differ only in where the "visit" line goes:
| Order | Rule | Example tree | Real-life use |
|---|---|---|---|
| Preorder | node, left, right | 1 2 4 5 3 6 |
a book's contents page; copying a tree |
| Inorder | left, node, right | 4 2 5 1 3 6 |
sorted order in a binary search tree (coming soon) |
| Postorder | left, right, node | 4 5 2 6 3 1 |
folder sizes (children first); deleting a tree |
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static void pre(Node n, List<Integer> out) {
if (n == null) return;
out.add(n.val);
pre(n.left, out);
pre(n.right, out);
}
static void in(Node n, List<Integer> out) {
if (n == null) return;
in(n.left, out);
out.add(n.val);
in(n.right, out);
}
static void post(Node n, List<Integer> out) {
if (n == null) return;
post(n.left, out);
post(n.right, out);
out.add(n.val);
}
public static void main(String[] args) {
Node t = new Node(1, new Node(2, new Node(4), new Node(5)),
new Node(3, null, new Node(6)));
List<Integer> a = new ArrayList<>(), b = new ArrayList<>(), c = new ArrayList<>();
pre(t, a);
in(t, b);
post(t, c);
System.out.println("pre: " + a);
System.out.println("in: " + b);
System.out.println("post: " + c);
}
}
Real output:
pre: [1, 2, 4, 5, 3, 6]
in: [4, 2, 5, 1, 3, 6]
post: [4, 5, 2, 6, 3, 1]
Every recursive tree function starts with the base case if (n == null) return;.
Problem statement: level order traversal
Binary Tree Level Order Traversal (LeetCode 102). Given the root of a binary tree, return the values level by level, each level from left to right.
example tree → [[1], [2, 3], [4, 5, 6]]
empty tree (null) → []
one node 7 → [[7]]
chain 1 → 2 → 3 (all left) → [[1], [2], [3]]
Brute force: one walk per level
Find the height h. Then for every depth d = 0 .. h - 1, walk the tree from the root and collect the nodes whose depth is d.
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static int height(Node n) {
return n == null ? 0 : 1 + Math.max(height(n.left), height(n.right));
}
static void collect(Node n, int depth, int d, List<Integer> out) {
if (n == null) return;
if (depth == d) { out.add(n.val); return; }
collect(n.left, depth + 1, d, out);
collect(n.right, depth + 1, d, out);
}
static List<List<Integer>> bruteLevels(Node root) {
List<List<Integer>> res = new ArrayList<>();
int h = height(root);
for (int d = 0; d < h; d++) {
List<Integer> level = new ArrayList<>();
collect(root, 0, d, level);
res.add(level);
}
return res;
}
public static void main(String[] args) {
Node t = new Node(1, new Node(2, new Node(4), new Node(5)),
new Node(3, null, new Node(6)));
System.out.println(bruteLevels(t));
}
}
Real output: [[1], [2, 3], [4, 5, 6]]. Correct.
Now a big tree: a complete tree 20 levels deep (2^20 - 1 ≈ 10 lakh nodes) under the root, plus a chain of 10,000 nodes on the right, so 10,000 levels:
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static int height(Node n) {
return n == null ? 0 : 1 + Math.max(height(n.left), height(n.right));
}
static void collect(Node n, int depth, int d, List<Integer> out) {
if (n == null) return;
if (depth == d) { out.add(n.val); return; }
collect(n.left, depth + 1, d, out);
collect(n.right, depth + 1, d, out);
}
static List<List<Integer>> bruteLevels(Node root) {
List<List<Integer>> res = new ArrayList<>();
int h = height(root);
for (int d = 0; d < h; d++) {
List<Integer> level = new ArrayList<>();
collect(root, 0, d, level);
res.add(level);
}
return res;
}
static Node full(int depth) {
if (depth == 0) return null;
return new Node(depth, full(depth - 1), full(depth - 1));
}
static Node bigTree() {
Node root = new Node(0, full(20), null), cur = root;
for (int i = 1; i < 10000; i++) {
cur.right = new Node(i);
cur = cur.right;
}
return root;
}
public static void main(String[] args) {
Node big = bigTree();
long t0 = System.nanoTime();
int levels = bruteLevels(big).size();
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println(levels + " levels, " + ms + " ms");
}
}
Real result: Time Limit Exceeded (about 36 seconds on my machine).
Why the brute force fails
Each of the 10,000 walks starts again at the root, and the ten-lakh-node complete part sits near the top, so every walk passes through all of it: about 10,000 × 10,00,000 = 1,000 crore node visits. In general the cost is O(n · h) for n nodes and height h: fine for a short, bushy tree, terrible for a tall one. We want one walk that hands us the nodes level by level.
The key insight: a queue, one level at a time
A queue is first in, first out, like the line at a ticket counter (episode 30). Breadth-first search (BFS) finishes a whole level before going deeper:
- Put the root in the queue.
- Before each level, save
size = q.size(): exactly the number of nodes in this level. - Poll
sizenodes. For each: record its value, offer its non-null children to the back of the queue (they are the next level). - Repeat until the queue is empty.
| Step | Polled | Offered | Level recorded | Queue after |
|---|---|---|---|---|
| start | [1] |
|||
| size = 1 | 1 | 2, 3 | [1] |
[2, 3] |
| size = 2 | 2, 3 | 4, 5, 6 | [2, 3] |
[4, 5, 6] |
| size = 3 | 4, 5, 6 | — | [4, 5, 6] |
[] |
Each node enters and leaves the queue exactly once: O(n).
The optimal solution in Java
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Deque<Node> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
Node n = q.poll();
level.add(n.val);
if (n.left != null) q.offer(n.left);
if (n.right != null) q.offer(n.right);
}
res.add(level);
}
return res;
}
public static void main(String[] args) {
Node t = new Node(1, new Node(2, new Node(4), new Node(5)),
new Node(3, null, new Node(6)));
System.out.println(levelOrder(t));
System.out.println(levelOrder(null));
System.out.println(levelOrder(new Node(7)));
System.out.println(levelOrder(new Node(1, new Node(2, new Node(3), null), null)));
}
}
Real output:
[[1], [2, 3], [4, 5, 6]]
[]
[[7]]
[[1], [2], [3]]
The big tree:
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Deque<Node> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
Node n = q.poll();
level.add(n.val);
if (n.left != null) q.offer(n.left);
if (n.right != null) q.offer(n.right);
}
res.add(level);
}
return res;
}
static Node full(int depth) {
if (depth == 0) return null;
return new Node(depth, full(depth - 1), full(depth - 1));
}
static Node bigTree() {
Node root = new Node(0, full(20), null), cur = root;
for (int i = 1; i < 10000; i++) {
cur.right = new Node(i);
cur = cur.right;
}
return root;
}
public static void main(String[] args) {
Node big = bigTree();
long t0 = System.nanoTime();
int levels = levelOrder(big).size();
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println(levels + " levels, " + ms + " ms");
}
}
Real output: 10000 levels in tens of milliseconds (59 ms in one run).
ArrayDeque is Java's fast general-purpose queue: offer adds at the back, poll removes from the front.
The same code in C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int val;
Node *left, *right;
Node(int v, Node* l = nullptr, Node* r = nullptr) : val(v), left(l), right(r) {}
};
void pre(Node* n, vector<int>& out) {
if (!n) return;
out.push_back(n->val); pre(n->left, out); pre(n->right, out);
}
void in(Node* n, vector<int>& out) {
if (!n) return;
in(n->left, out); out.push_back(n->val); in(n->right, out);
}
void post(Node* n, vector<int>& out) {
if (!n) return;
post(n->left, out); post(n->right, out); out.push_back(n->val);
}
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> res;
if (!root) return res;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
vector<int> level;
for (int i = 0; i < size; i++) {
Node* n = q.front(); q.pop();
level.push_back(n->val);
if (n->left) q.push(n->left);
if (n->right) q.push(n->right);
}
res.push_back(level);
}
return res;
}
int main() {
Node* t = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3, nullptr, new Node(6)));
vector<int> a, b, c;
pre(t, a); in(t, b); post(t, c);
for (auto* v : {&a, &b, &c}) { for (int x : *v) cout << x << ' '; cout << '\n'; }
for (auto& level : levelOrder(t)) { for (int x : level) cout << x << ' '; cout << "| "; }
cout << '\n';
}
Output: 1 2 4 5 3 6, 4 2 5 1 3 6, 4 5 2 6 3 1, then 1 | 2 3 | 4 5 6 |.
The same code in Python
from collections import deque
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def pre(n, out):
if n is None:
return
out.append(n.val); pre(n.left, out); pre(n.right, out)
def inorder(n, out):
if n is None:
return
inorder(n.left, out); out.append(n.val); inorder(n.right, out)
def post(n, out):
if n is None:
return
post(n.left, out); post(n.right, out); out.append(n.val)
def level_order(root):
res = []
if root is None:
return res
q = deque([root])
while q:
level = []
for _ in range(len(q)): # len(q) is read once, before the loop starts
n = q.popleft()
level.append(n.val)
if n.left:
q.append(n.left)
if n.right:
q.append(n.right)
res.append(level)
return res
t = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6)))
for f in (pre, inorder, post):
out = []; f(t, out); print(f.__name__, out)
print(level_order(t), level_order(None))
Output: pre [1, 2, 4, 5, 3, 6], inorder [4, 2, 5, 1, 3, 6], post [4, 5, 2, 6, 3, 1], [[1], [2, 3], [4, 5, 6]] [].
Three real bugs
Bug 1: i < q.size() in the loop
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Deque<Node> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
List<Integer> level = new ArrayList<>();
for (int i = 0; i < q.size(); i++) {
Node n = q.poll();
level.add(n.val);
if (n.left != null) q.offer(n.left);
if (n.right != null) q.offer(n.right);
}
res.add(level);
}
return res;
}
public static void main(String[] args) {
Node t = new Node(1, new Node(2, new Node(4), new Node(5)),
new Node(3, null, new Node(6)));
System.out.println(levelOrder(t));
}
}
Real output: [[1, 2, 3], [4, 5], [6]]. The queue grows while children are offered, so the loop runs into the next level. Save the size first.
Bug 2: offering null children
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Deque<Node> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
Node n = q.poll();
level.add(n.val);
q.offer(n.left);
q.offer(n.right);
}
res.add(level);
}
return res;
}
public static void main(String[] args) {
Node t = new Node(1, new Node(2, new Node(4), new Node(5)),
new Node(3, null, new Node(6)));
System.out.println(levelOrder(t));
}
}
Real output:
Exception in thread "main" java.lang.NullPointerException
at java.base/java.util.ArrayDeque.addLast(ArrayDeque.java:302)
at java.base/java.util.ArrayDeque.offerLast(ArrayDeque.java:351)
at java.base/java.util.ArrayDeque.offer(ArrayDeque.java:507)
Node 3 has no left child, so null was offered, and ArrayDeque does not allow null elements.
Bug 3: recursion without a base case
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static void in(Node n, List<Integer> out) {
in(n.left, out);
out.add(n.val);
in(n.right, out);
}
public static void main(String[] args) {
Node t = new Node(1, new Node(2, new Node(4), new Node(5)),
new Node(3, null, new Node(6)));
List<Integer> out = new ArrayList<>();
in(t, out);
System.out.println(out);
}
}
Real output:
Exception in thread "main" java.lang.NullPointerException: Cannot read field "left" because "<parameter1>" is null
at Main.in(Main.java:11)
The recursion walked past a leaf into null and tried to read null.left.
Complexity
| Algorithm | Time | Extra space |
|---|---|---|
| Preorder / inorder / postorder (recursive) | O(n) | O(h) recursion stack |
| Level order, one walk per level | O(n · h) | O(h) recursion |
| Level order with a queue (BFS) | O(n) | O(w) queue, w = widest level (about n/2 for a complete tree) |
On a very tall tree (tens of thousands of levels) the recursive versions can throw StackOverflowError; iterative versions with an explicit stack or queue avoid that.
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
for (int i = 0; i < q.size(); i++) |
[[1, 2, 3], [4, 5], [6]] |
the queue grows during the level | int size = q.size(); before the loop |
q.offer(n.left) without a check |
java.lang.NullPointerException in ArrayDeque.addLast |
ArrayDeque rejects null |
if (n.left != null) q.offer(n.left); |
No if (n == null) return; |
NullPointerException: Cannot read field "left" |
the recursion goes past the leaves | base case first |
Not handling root == null in BFS |
NullPointerException |
null offered as the root |
if (root == null) return res; |
A stack (push/pop) instead of a queue |
nodes come out newest first | last in, first out | offer / poll on a queue |
| Moving the visit line by mistake | wrong order (e.g. preorder instead of inorder) | the order is only the position of that line | node-left-right / left-node-right / left-right-node |
Mini project: the school announcement
Build the school as a binary tree (principal, 2 vice principals, up to 2 class teachers each) with names as values (Node with a String). Print the announcement order level by level, like Level 0: Principal, Level 1: VP Asha, VP Ravi, Level 2: ..., and print the total number of people with a postorder count (each node = 1 + left count + right count).
Practice
- Right side view (LeetCode 199): the last value of each level.
Solution
In BFS, record n.val only when i == size - 1. Example tree → [1, 3, 6].
- Zigzag level order (LeetCode 103): left to right, then right to left, alternating.
Solution
Do normal BFS, and reverse every second level (Collections.reverse(level) when the level number is odd). Example tree → [[1], [3, 2], [4, 5, 6]].
- Average of levels (LeetCode 637).
Solution
In BFS, add up the size values as long and divide by size. Example tree → [1.0, 2.5, 5.0].
- Preorder without recursion.
Solution
Use a stack. Push the root; while the stack is not empty, pop a node, visit it, then push its right child and then its left child (so the left one is popped first).
static List<Integer> preIter(Node root) {
List<Integer> out = new ArrayList<>();
Deque<Node> st = new ArrayDeque<>();
if (root != null) st.push(root);
while (!st.isEmpty()) {
Node n = st.pop();
out.add(n.val);
if (n.right != null) st.push(n.right);
if (n.left != null) st.push(n.left);
}
return out;
}
Example tree → [1, 2, 4, 5, 3, 6].
Quick quiz
Which traversal prints 4 5 2 6 3 1 for the example tree? Preorder, inorder, postorder or level order?
Answer
Postorder. Every parent comes after its children (4 and 5 before 2, 6 before 3, and the root 1 last): left, right, node.
Interview questions
- What is the difference between DFS and BFS on a tree? DFS goes deep down one branch first (recursion or a stack); BFS finishes each level first (a queue).
- Name the three DFS orders and one use of each. Preorder (copy/serialize a tree), inorder (sorted output of a BST), postorder (compute sizes or delete a tree; children before parent).
- How do you know where one level ends in BFS? Save
q.size()before processing the level. - Time and space of level order? O(n) time, O(w) space for the widest level.
- When can recursion fail on trees? Very tall (skewed) trees:
StackOverflowError. Use an explicit stack. - Why does
ArrayDequethrow onoffer(null)? It usesnullinternally to mark empty slots, so it forbidsnullelements; check children before offering.
Glossary
| Term | Meaning |
|---|---|
| Tree | Nodes connected by edges, with one root and no cycles; every node except the root has one parent |
| Node | One item of the tree (here: a value plus left and right references) |
| Edge | The link between a parent and a child |
| Root | The top node; it has no parent |
| Parent / child | A node and a node directly below it |
| Leaf | A node with no children |
| Depth | Number of edges from the root to a node |
| Level | All nodes with the same depth |
| Height | Number of levels in the tree |
| Binary tree | A tree where every node has at most two children, left and right |
| Traversal | Visiting every node exactly once in some order |
| DFS (depth-first search) | Go as deep as possible down one branch before the next |
| Preorder / inorder / postorder | DFS orders: node-left-right / left-node-right / left-right-node |
| BFS (breadth-first search) | Visit all nodes of one level before the next, using a queue |
| Queue | First in, first out: offer at the back, poll from the front |
ArrayDeque |
Java's array-based double-ended queue; no null elements allowed |
| Base case | The condition that stops recursion (n == null) |
StackOverflowError |
Java's error when recursion goes too deep |
Summary
- A tree stores "who is under whom": root, parents, children, leaves, levels. A binary tree node has
leftandright. - Preorder, inorder, postorder: the same three-line recursion with the visit line moved; always start with
if (n == null) return;. - Level order by walking the tree once per level is O(n · h): TLE on a tall tree. BFS with a queue and
size = q.size()per level is O(n).
Next episode: Maximum depth and diameter of a binary tree.