Binary trees and traversals

You’ll recognise it when

• The input is a TreeNode with left and right, or a list like [5, 3, 8, 1, 4, null, 9] that describes one.
• You need the values of a binary search tree in sorted order, or the k-th smallest: that’s inorder.
• The answer for a node depends on answers from its children: height, diameter, “is it balanced”, subtree sums. That’s postorder, usually written as recursion.
• The question says “per level”: the average of each row, the rightmost node you’d see, zigzag order. That’s level order with a queue.
• You need to copy or save a tree and rebuild it later: preorder with markers for missing children.

Level order is BFS and the other three are DFS; a tree is just a graph with no cycles, so you never need a visited set.

The idea

A binary tree is a set of nodes where each node has at most two children, a left and a right. The top node is the root, nodes with no children are leaves, and a node plus everything below it is a subtree. A node’s depth is how many edges it sits below the root; the tree’s height is the largest depth.

Every traversal visits every node once. What differs is when you output a node compared with its two subtrees. Picture walking around the outside of the tree, starting at the root and keeping the tree on your left hand. You pass each node three times: on the way down, underneath it (between its left and right subtrees), and on the way back up.

• Preorder outputs a node the first time you pass it: node, left, right.
• Inorder outputs it the second time: left, node, right.
• Postorder outputs it the last time: left, right, node.
• Level order ignores the walk and reads the tree row by row, top to bottom.

In a binary search tree (BST), everything in a node’s left subtree is smaller and everything in its right subtree is bigger. Inorder visits the left side, then the node, then the right side, so on a BST it reads the values in sorted order.

How it works

Recursively, inorder is three lines: traverse the left subtree, output the node, traverse the right subtree. The iterative version does the same thing with its own stack instead of the call stack, which matters on deep trees. The graphic runs it on a BST of 9 nodes, laid out so each node has its own column; scroll through the steps and it follows along.

Why it’s right: a node is popped only after the inner loop has pushed and finished everything to its left, and the stack always holds the path of ancestors still waiting for their left side to finish, deepest on top. So each node comes out after its left subtree and before its right one, which is exactly inorder.

Now open edit and try order = pre, post and level. Same tree, different rule for when a node leaves:

• pre: pop a node and output it at once, then push its right child and then its left, so the left one is on top and goes first. Output: 6 3 1 2 5 4 9 8 11.
• post: like inorder, but a node stays on the stack until its right subtree is also done. Output: 2 1 4 5 3 8 11 9 6, root last.
• level: a queue instead of a stack. Taking exactly len(queue) nodes per round gives one level per round: [6], [3, 9], [1, 5, 8, 11], [2, 4].

from collections import deque


class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def inorder(root):
    """Values in left, node, right order, with an explicit stack."""
    out, stack = [], []
    node = root
    while node or stack:
        while node:                         # go as far left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.val)
        node = node.right
    return out


def level_order(root):
    """Values level by level, each level left to right."""
    levels = []
    queue = deque([root] if root else [])
    while queue:
        level = []
        for _ in range(len(queue)):         # exactly the nodes of this level
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        levels.append(level)
    return levels

#include <deque>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left = nullptr;
    TreeNode* right = nullptr;
    explicit TreeNode(int v) : val(v) {}
};

// Values in left, node, right order, with an explicit stack.
vector<int> inorder(TreeNode* root) {
    vector<int> out;
    vector<TreeNode*> stack;
    TreeNode* node = root;
    while (node || !stack.empty()) {
        while (node) {                          // go as far left as possible
            stack.push_back(node);
            node = node->left;
        }
        node = stack.back();
        stack.pop_back();
        out.push_back(node->val);
        node = node->right;
    }
    return out;
}

// Values level by level, each level left to right.
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> levels;
    deque<TreeNode*> queue;
    if (root) queue.push_back(root);
    while (!queue.empty()) {
        vector<int> level;
        size_t size = queue.size();             // exactly the nodes of this level
        for (size_t i = 0; i < size; i++) {
            TreeNode* node = queue.front();
            queue.pop_front();
            level.push_back(node->val);
            if (node->left) queue.push_back(node->left);
            if (node->right) queue.push_back(node->right);
        }
        levels.push_back(level);
    }
    return levels;
}

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

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

class Traversals {
    // Values in left, node, right order, with an explicit stack.
    static List<Integer> inorder(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {                  // go as far left as possible
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            out.add(node.val);
            node = node.right;
        }
        return out;
    }

    // Values level by level, each level left to right.
    static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        Deque<TreeNode> queue = new ArrayDeque<>();
        if (root != null) queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int size = queue.size();                // exactly the nodes of this level
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            levels.add(level);
        }
        return levels;
    }
}

Most tree problems are solved recursively. Ask: what do I need from each child? Write a function that takes a node, gets an answer from its left child and from its right child, and combines them. An empty child returns a base value. For the height (number of nodes on the longest path down):

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

Sometimes the answer isn’t what the parent needs. The diameter is the longest path between any two nodes, in edges. The longest path through a node goes down both sides, so it’s left_height + right_height, but the parent can only extend one side, so the function returns the height and keeps the best path in a separate variable:

def diameter(root):
    best = 0
    def height(node):
        nonlocal best
        if node is None:
            return 0
        l, r = height(node.left), height(node.right)
        best = max(best, l + r)      # the longest path bending at this node
        return 1 + max(l, r)         # what the parent needs
    height(root)
    return best

Both are postorder: a node’s work happens after both children have reported back.

Why it’s O(n)

Each node is pushed once and popped once (or enqueued and dequeued once), with O(1) work each time, so every traversal is O(n) for n nodes.

The extra space is the frontier. The stack holds one path from the root, so it’s O(h) where h is the height: about log₂ n for a balanced tree, but n for a tree that’s one long chain. The queue holds at most one full level plus part of the next, O(w) where w is the widest level, up to about n/2 for a complete tree.

Common mistakes

def walk(node): ...walk(node.left)...   # ✗ RecursionError on a 10⁵-node chain
stack.append(node); node = node.left     # ✓ the depth lives in a list

node.left.val < node.val < node.right.val    # ✗ misses deeper values
lo < node.val < hi                           # ✓ bounds from all ancestors

return l + r            # ✗ a path, not a height
return 1 + max(l, r)    # ✓ height up; best = max(best, l + r) on the side

stack += [node.left, node.right]   # ✗ right subtree comes out first
stack += [node.right, node.left]   # ✓ left on top

Variations

• Maximum depth. 1 + max(depth(left), depth(right)), with 0 for an empty tree. Or count the rounds of a level-order traversal.
• Diameter and friends. Return one thing to the parent (a height, a best single-branch sum) and keep the overall best in a separate variable. The same shape solves “maximum path sum” and “longest path with equal values”.
• Validate a BST. Pass (lo, hi) bounds down: going left sets hi to the node’s value, going right sets lo. Or run inorder and check each value is bigger than the one before.
• Lowest common ancestor. Recurse: return the node if it is one of the two targets, otherwise ask both children. If both sides return something, this node is the answer; else pass up whichever side found one. In a BST, just walk down from the root toward both values until they split.
• Serialize and deserialize. Write preorder with a marker for every missing child (1 2 # # 3 # #). The markers pin down the shape, so reading the list back in the same order, one token at a time, rebuilds the exact tree in O(n).