SyntaxPilot
Courses/DSA and Coding Problems/Lesson 36
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 36 of 90

Trees: preorder, inorder, postorder and level order

queued

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:

  1. Put the root in the queue.
  2. Before each level, save size = q.size(): exactly the number of nodes in this level.
  3. Poll size nodes. For each: record its value, offer its non-null children to the back of the queue (they are the next level).
  4. 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

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

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

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

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

  1. 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).
  2. 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).
  3. How do you know where one level ends in BFS? Save q.size() before processing the level.
  4. Time and space of level order? O(n) time, O(w) space for the widest level.
  5. When can recursion fail on trees? Very tall (skewed) trees: StackOverflowError. Use an explicit stack.
  6. Why does ArrayDeque throw on offer(null)? It uses null internally to mark empty slots, so it forbids null elements; 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 left and right.
  • 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.