On this page

Trees

Trees are hierarchical data structures that model real-world relationships: file systems, DOM trees, organizational charts, parse trees, decision trees. In interviews, tree problems test your comfort with recursion. In production, trees power databases (B-trees), autocomplete (tries), compilers (ASTs), and range queries (segment trees).

This page is the overview lesson of Module 3 — Trees in DSA: Zero to Mastery. It gives you the vocabulary, the four traversals, the handful of proofs that every later lesson reuses, and a tour of the tree families the module covers in depth. Read it first; each section ends with a pointer to the lesson that goes deeper.

How this module is organised

Module 3 has one overview (this page), thirteen deep lessons and a capstone. The order is deliberate: first the shape and how to walk it, then ordered trees (BSTs) and how to keep them balanced, then priority structures (heaps), then trees built for one job each (prefix search, range queries, ancestor queries, geometry).

#LessonOne line on what it gives you
0Module 3 indexThe module map, time estimates and how to study it.
1Trees (Overview)This page: vocabulary, traversals, core proofs, a tour of every tree family.
2Binary Trees & TraversalsEvery traversal recursively, iteratively and with Morris threading; building trees from traversals.
3Tree Problem PatternsThe recipes: return-a-value-up, pass-state-down, global best, path problems, rerooting.
4Binary Search TreesThe ordering invariant, search/insert/delete, successor, floor/ceiling and rank queries.
5Balanced BSTs: AVL & Red-Black TreesRotations, the AVL and red-black invariants, and why they force height.
6Treaps, Splay Trees & Skip ListsBalance by randomness or by amortization; split/merge treaps; why Redis uses a skip list.
7Heaps & Priority QueuesThe array-backed complete tree, heapify, top-K, two heaps, k-way merge, timers.
8Tries in DepthPrefix trees, compressed (radix) tries, binary tries for XOR problems, longest-prefix match.
9Segment Trees in DepthRange queries with point and range updates, lazy propagation, merging custom monoids.
10Fenwick TreesPrefix sums in with one array and the lowest-set-bit trick.
11Sparse Tables, Sqrt Decomposition & Mo's Algorithm static range-min, block decomposition, and offline query reordering.
12LCA, Binary Lifting & Euler TourAncestor queries in , and flattening a tree into an array.
13Heavy-Light & Centroid DecompositionPath queries via chains, and divide-and-conquer on trees.
14Spatial TreesInterval trees, k-d trees, quadtrees and R-trees for geometric queries.
15Capstone: A Range-Query EngineBuild and benchmark a range-query service on the structures above.
flowchart LR
    OV["Trees overview"] --> BT["Binary trees and traversals"]
    BT --> TP["Tree problem patterns"]
    TP --> BST["Binary search trees"]
    BST --> BAL["AVL and red-black"]
    BAL --> TR["Treaps, splay, skip lists"]
    TR --> HP["Heaps and priority queues"]
    HP --> TRIE["Tries"]
    TRIE --> SEG["Segment trees"]
    SEG --> FEN["Fenwick trees"]
    FEN --> SP["Sparse tables and sqrt"]
    SP --> LCA["LCA and binary lifting"]
    LCA --> HLD["Heavy-light and centroid"]
    HLD --> SPA["Spatial trees"]
    SPA --> CAP["Capstone: range-query engine"]

Prerequisites. You need recursion and induction (Recursion & Mathematical Induction), because nearly every tree algorithm is a recursive function and nearly every tree proof is an induction. You need Stacks and Queues, Deques & Circular Buffers, because depth-first traversal is a stack and breadth-first traversal is a queue. Big-O and amortized analysis come from Complexity Analysis. The previous module ends with Capstone: A Sorting Library With Benchmarks; Binary Search Mastery is the direct ancestor of the binary search tree.

Module 3 at a glance

A tree is a connected graph with no cycles — equivalently, a hierarchy in which every element except the root has exactly one parent. That single restriction buys a great deal. Because there is exactly one path between any two nodes, recursion on a tree never revisits anything, so a whole family of problems that are hard on general graphs becomes a single pass. And because a balanced tree of nodes is only about levels deep, trees turn linear scans into logarithmic searches: a million keys need about 20 comparisons, a billion about 30.

Module 3 teaches trees in two halves. The first half is about trees as data: how to traverse them, how to write recursive functions over them with precise contracts, and how to keep a search tree balanced so its height stays logarithmic. The second half is about trees as indexes over other data: heaps that keep the minimum on top, tries that index strings by prefix, and segment trees, Fenwick trees and sparse tables that answer range queries on an array in or . It ends with path queries on trees and with spatial trees.

The module is in the DSA: Zero to Mastery course. Previous module: Module 2 · Searching & Sorting. Next: Module 4 (graphs).

What this module covers

Fourteen lessons and a capstone, in four arcs.

Arc 1 — binary trees and recursion. The Trees overview, then Binary Trees & Traversals (shape facts, every traversal, Morris, serialization, construction) and Tree Problem Patterns (the top-down and bottom-up templates, with proofs for diameter, path sums and LCA).

Arc 2 — ordered trees. Binary Search Trees, why they degenerate, and the fixes: rotations in Balanced BSTs: AVL & Red-Black Trees, randomization and self-adjustment in Treaps, Splay Trees & Skip Lists.

Arc 3 — trees as indexes. Heaps & Priority Queues, Tries in Depth, and the range-query trio: Segment Trees in Depth, Fenwick Trees and Sparse Tables, Sqrt Decomposition & Mo's Algorithm.

Arc 4 — queries on trees and space. LCA, Binary Lifting & Euler Tour flattens a tree into an array so Arc 3 applies to subtrees; Heavy-Light & Centroid Decomposition extends that to paths; Spatial Trees indexes intervals, points and rectangles.

Capstone. Capstone: A Range-Query Engine: one API over a segment tree, a Fenwick tree and sqrt decomposition, with sum, min and max under point and range updates, verified against brute force and benchmarked.

Optional deep dive. Advanced Data Structures — a second angle on Arcs 2 and 3.

Why in this order

Traversals come first because every later lesson is a traversal with bookkeeping: a BST search is a root-to-leaf walk, a segment-tree query a pruned preorder, an Euler tour a DFS writing timestamps. The patterns lesson's habit — state a recursive function's contract, null case included, and prove it by induction — is what makes rotations and lazy propagation tractable later.

BSTs precede balancing because you must see a tree degenerate before rotations make sense. Heaps follow as the counterexample: they give up full ordering for a complete shape and an array layout, which segment trees then reuse. Fenwick trees follow segment trees as their compressed form for invertible operations. LCA and heavy-light decomposition combine everything before them; spatial trees bridge to geometry and Archon's spatial indexing page.

flowchart TD
    M2["Module 2 · Searching & Sorting"] --> OV["Trees overview"]
    OV --> BT["Binary Trees & Traversals"]
    BT --> TP["Tree Problem Patterns"]
    TP --> BST["Binary Search Trees"]
    BST --> BAL["Balanced BSTs"]
    BAL --> TSS["Treaps, Splay & Skip Lists"]
    BT --> HP["Heaps & Priority Queues"]
    BT --> TR["Tries"]
    HP --> SEG["Segment Trees"]
    SEG --> FEN["Fenwick Trees"]
    SEG --> SPA["Sparse Tables & Sqrt"]
    TP --> LCA["LCA & Binary Lifting"]
    SPA --> LCA
    LCA --> HLD["Heavy-Light & Centroid"]
    BAL --> SPT["Spatial Trees"]
    FEN --> CAP["Capstone: Range-Query Engine"]
    SPA --> CAP
    CAP --> M4["Module 4 · Graphs"]

Arrows mean "read this first". Arc 2 (ordered trees) and Arc 3 (heaps, tries, range queries) are independent after the patterns lesson and can be interleaved.

Prerequisites

From Module 0: Recursion & Mathematical Induction (nearly every proof here is induction on subtree size) and Complexity Analysis, including amortized analysis. From Module 1: Stacks and Queues, Deques & Circular Buffers (iterative DFS and BFS), Prefix Sums, which range trees generalise, and Hash Tables. From Module 2: Binary Search Mastery — a BST is binary search as a data structure — and Heap Sort.

You need one of Python 3.12+, Java 21, C++20 or TypeScript (Node 22+). Every canonical implementation is given in all four, builds its test trees from LeetCode-style level-order arrays, and checks itself with asserts.

How to study this module

Draw the tree. Sketch each example's level-order array before reading the trace. Tree bugs are usually shape bugs — a one-sided node, a skewed chain, an empty subtree — visible on paper long before a debugger shows them.

Write the contract before the code. For every recursive function, write one comment: what it receives, what it returns, and what it returns for null. The patterns lesson shows how much of tree programming is getting that comment right; the balanced-tree and segment-tree lessons depend on it.

Test on four shapes. Empty tree, single node, a path (all left or all right children), and a perfect tree. The path catches recursion-depth and problems; the perfect tree catches width problems in BFS. Every canonical implementation in this module includes at least two of these in its asserts.

Use a brute-force oracle for the range structures. Segment trees, Fenwick trees and sparse tables are easy to get subtly wrong at boundaries. Compare against a plain array scan on thousands of random operations, exactly as Testing & Debugging Algorithms prescribes — the capstone is built around this.

Climb the practice ladders in two passes. Do the first eight problems of each ladder as you read, and return to the hard tail after the module is finished; many of the hard tree problems combine two lessons.

Start with the Trees overview, then follow the table. Previous module: Searching & Sorting. Course map: DSA: Zero to Mastery.

Why trees exist

Arrays and linked lists are one-dimensional: every element has at most one successor. That is the wrong shape for most data people actually have. A file lives in a folder that lives in a folder. An HTML element sits inside another element. An arithmetic expression like (a + b) * c has an operator whose operands are themselves expressions. A company has a CEO, VPs under the CEO, and managers under the VPs. All of these are hierarchies: each item has exactly one parent and any number of children, and the interesting questions ("what is inside this folder?", "what does this expression evaluate to?") are answered by recursing into the children.

The second reason is speed. A sorted array supports binary search in but insertion costs , because everything after the insertion point shifts. A linked list inserts in once you are at the right spot but needs to get there. A balanced search tree gets both: search and insert, because a tree of height can hold up to keys, so a tree holding a billion keys can be about 30 levels deep. Push the branching factor from 2 to a few hundred and you get the B-tree, where a billion keys fit in 4 levels — which is why every mainstream database index is one.

The mathematics is old. Arthur Cayley counted trees in 1857 while studying chemical isomers, and in 1889 proved that there are labelled trees on vertices. The data-structure history starts in the late 1950s and 1960s: binary search trees appear in the early literature on symbol tables, the AVL tree (Adelson-Velsky and Landis, 1962) was the first self-balancing BST, the trie was described by de la Briandais (1959) and named by Fredkin (1960), the heap came with Williams's heapsort (1964), the B-tree with Bayer and McCreight (1970, published 1972), and the red-black tree with Guibas and Sedgewick (1978). Knuth's The Art of Computer Programming, Volume 1, §2.3 is still the definitive treatment of tree terminology and traversal; Volume 3, §6.2 covers search trees.

Where you will meet trees in this course and beyond: every recursive problem on a hierarchy, every ordered map (TreeMap, std::map), every priority queue, every database index, every compiler, every router's forwarding table, and every graph algorithm that builds a spanning tree or a shortest-path tree (Graphs treats trees as the special case of graphs that they are).

Pattern triggers

These are the literal signals in a problem statement that should make you think "tree".

If the problem says or has…Think of…Lesson
"binary tree", "root", TreeNode in the signatureRecursion: solve left, solve right, combineTree problem patterns
"level by level", "zigzag", "right side view", "minimum depth"BFS with a queue, processing one level per loopTraversals
"serialize", "copy", "clone", "construct from preorder/inorder"Preorder (root first) plus a marker for null childrenBinary trees & traversals
"sorted order", "k-th smallest", "validate BST", "successor"Inorder traversal of a BST is sortedBinary search trees
"free/delete the tree", "evaluate expression", "subtree sums", "height of each node"Postorder: children before the parentTraversals
"longest path between any two nodes", "max path sum"Return one value up (best single branch), keep a global best (two branches)Diameter
"lowest common ancestor", "distance between two nodes"LCA by recursion; binary lifting for many queriesLCA & binary lifting
"insert/delete and query the min/max repeatedly", "k-th largest", "schedule by priority"Heap / priority queueHeaps & priority queues
"ordered set with insert, delete, floor, ceiling, rank"Balanced BST (TreeMap, std::set, SortedList)Balanced BSTs
"prefix", "autocomplete", "dictionary of words", "maximum XOR pair"Trie (character or bit trie)Tries
"range sum/min/max with updates", "count of elements in range after updates"Segment tree or Fenwick treeSegment trees, Fenwick trees
"static array, many range-min queries"Sparse tableSparse tables
" nodes and edges", "connected, no cycles", "company hierarchy"A general (n-ary) tree given as an edge list: DFS from a rootGraphs
"path sum/max between two nodes, with updates"Heavy-light decompositionHeavy-light & centroid
"nearest point", "rectangles overlapping", "intervals containing x"Spatial trees: k-d tree, R-tree, interval treeSpatial trees

A useful negative trigger: if the "tree" can have a node with two parents, it is a DAG or a general graph, and tree recursion will double-count or loop. Check for that before you write solve(left) + solve(right).

Core Concepts

A tree is a connected, acyclic graph with nodes and edges. Every tree has exactly one root, and every node has exactly one parent (except the root).

Correction: a tree has a root only once you choose one

As a graph, a tree (a free tree) has no distinguished root; any node can serve. "Exactly one root" and "every node has one parent" describe a rooted tree, which you get by picking a root and orienting every edge away from it. Data-structure trees are always rooted; trees that arrive as an edge list (CSES, Codeforces) are free, and the first step is to pick node 1 as the root and run a DFS to compute parents.

graph TD
    A["Root (1)"] --> B["2"]
    A --> C["3"]
    B --> D["4"]
    B --> E["5"]
    C --> F["6"]
    C --> G["7"]
    style A fill:#4CAF50,color:#fff
    style D fill:#FFC107
    style E fill:#FFC107
    style F fill:#FFC107
    style G fill:#FFC107

Terminology:

  • Root: The topmost node (no parent)
  • Leaf: A node with no children
  • Height: Longest path from root to a leaf
  • Depth: Distance from the root to a node
  • Subtree: A node and all its descendants

Terminology table

The full vocabulary, with each term evaluated on the 7-node tree above (root 1; children 2 and 3; leaves 4, 5, 6, 7).

TermPrecise meaningIn the example
Node (vertex)An element of the tree7 nodes
EdgeA parent–child link6 edges ()
RootThe node with no parent (after rooting)1
Parent / child is the parent of if the edge exists2 is the parent of 4 and 5
SiblingsNodes with the same parent4 and 5; 6 and 7; 2 and 3
Leaf (external node)A node with no children4, 5, 6, 7
Internal nodeA node with at least one child1, 2, 3
Ancestor / descendant is an ancestor of if is on the path from the root to (a node is usually counted as its own ancestor in LCA definitions)Ancestors of 6: 3, 1 (and 6 itself)
Subtree of and all its descendantsSubtree of 2 = {2, 4, 5}
Depth of Number of edges from the root to depth(1) = 0, depth(5) = 2
LevelAll nodes with the same depthLevel 1 = {2, 3}
Height of Number of edges on the longest downward path from to a leafheight(2) = 1, height(4) = 0
Height of the treeHeight of the root; empty tree has height by this convention2
"Max depth" (LeetCode)Number of nodes on the longest root-to-leaf path = height + 13
Degree of Number of children (in a rooted tree)degree(1) = 2, degree(4) = 0
Arity / branching factorMaximum number of children allowed2 (binary)
PathA sequence of nodes joined by edges, no repeats4 – 2 – 1 – 3 – 6
DiameterLength (edges) of the longest path between any two nodes4 (e.g. 4 to 6)
ForestA set of disjoint trees (a tree minus its root)Removing 1 leaves two trees
Full binary treeEvery node has 0 or 2 childrenYes
Complete binary treeEvery level full except possibly the last, which is filled left to rightYes
Perfect binary treeAll internal nodes have 2 children and all leaves share one depth; has nodesYes:
BalancedHeight is ; AVL's specific rule is "subtree heights differ by at most 1 at every node"Yes
Degenerate (skewed)Every node has at most one child; a linked list in disguise, height No

Height has two conventions

Textbooks (CLRS, Sedgewick) measure height in edges, so a single node has height 0 and an empty tree . LeetCode's "maximum depth" counts nodes, so a single node has depth 1 and an empty tree 0. Both are fine; mixing them inside one solution is a classic off-by-one. Decide at the top of the function which one height(None) returns.

Representations

How a tree is laid out in memory decides which operations are cheap.

RepresentationWhat is storedGood forWeakness
Linked nodes (left, right pointers)One object per nodeInterview problems, BSTs, anything that changes shapePointer chasing: each step can be a cache miss
Implicit array (children of at , )Values onlyComplete trees: heaps, segment treesWastes space on sparse or skewed trees
Parent array (parent[v])One integer per nodeUnion-find, walking up to the root, LCA by binary liftingFinding children needs a scan
Adjacency listNeighbour list per nodeGeneral trees from an edge list (CSES, Codeforces)Must pass parent in DFS to avoid walking back up
First-child / next-siblingTwo pointers per nodeTurning any n-ary tree into a binary tree (Knuth §2.3.2)Child access is a list walk
Euler-tour arrayEntry/exit times per nodeSubtree queries become range queriesStatic: rebuild after shape changes

The memory-layout side of this (why the array form is several times faster to traverse than the pointer form) is covered in How Data Structures Live in Memory.

Binary Tree

Each node has at most two children: left and right.

The canonical node type, with the 7-node example tree built and checked in each language. The same tree is the test input for every code group on this page.

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


# The 7-node tree used throughout this page.
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6), TreeNode(7)))
assert root.left.right.val == 5 and root.right.left.val == 6
assert root.left.left.left is None
print("ok")
public class BinaryTreeNode {
    static final class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode(int val) { this(val, null, null); }

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

    static void check(boolean cond) { if (!cond) throw new AssertionError(); }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1,
                new TreeNode(2, new TreeNode(4), new TreeNode(5)),
                new TreeNode(3, new TreeNode(6), new TreeNode(7)));
        check(root.left.right.val == 5 && root.right.left.val == 6);
        check(root.left.left.left == null);
        System.out.println("ok");
    }
}
#include <cassert>
#include <iostream>

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

void destroy(TreeNode* n) {
    if (!n) return;
    destroy(n->left);
    destroy(n->right);
    delete n;
}

int main() {
    TreeNode* root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)),
                                  new TreeNode(3, new TreeNode(6), new TreeNode(7)));
    assert(root->left->right->val == 5 && root->right->left->val == 6);
    assert(root->left->left->left == nullptr);
    destroy(root);
    std::cout << "ok\n";
}
class TreeNode<T> {
  val: T;
  left: TreeNode<T> | null;
  right: TreeNode<T> | null;

  constructor(val: T, left: TreeNode<T> | null = null, right: TreeNode<T> | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

// The 7-node tree used throughout this page.
const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3, new TreeNode(6), new TreeNode(7)));
if (root.left!.right!.val !== 5 || root.right!.left!.val !== 6) throw new Error("shape");
if (root.left!.left!.left !== null) throw new Error("leaf");
console.log("ok");

In C++ an interview answer usually leaks the nodes; production code would use std::unique_ptr<TreeNode> children or an arena. The destroy function above is itself a postorder traversal — children are freed before their parent, which is exactly why postorder exists.

Traversals

The four fundamental traversals differ in when they process the current node relative to its children.

graph TD
    A["1"] --> B["2"]
    A --> C["3"]
    B --> D["4"]
    B --> E["5"]
    C --> F["6"]
    C --> G["7"]
TraversalOrderResultUse Case
InorderLeft → Root → Right4, 2, 5, 1, 6, 3, 7BST gives sorted order
PreorderRoot → Left → Right1, 2, 4, 5, 3, 6, 7Serialize/copy a tree
PostorderLeft → Right → Root4, 5, 2, 6, 7, 3, 1Delete tree, evaluate expressions
Level-orderLevel by level1, 2, 3, 4, 5, 6, 7BFS, shortest path in tree

Intuition: one walk, three moments

The three depth-first orders are not three algorithms. They are one walk around the tree — start at the root, go down the left side, come back up, go down the right side, come back up — and every node is passed three times: on the way down (before the left subtree), between the subtrees, and on the way back up (after the right subtree). Preorder writes the node at the first moment, inorder at the second, postorder at the third. This "Euler tour" view explains the use cases: preorder sees a parent before any descendant (good for copying top-down), postorder sees a parent after all descendants (good for computing anything that depends on children: sizes, heights, freeing memory), and inorder sees the node exactly between its left and right subtrees (good for ordered trees).

flowchart LR
    V["visit(node)"] --> P["moment 1: preorder emits"]
    P --> L["recurse into left subtree"]
    L --> I["moment 2: inorder emits"]
    I --> R["recurse into right subtree"]
    R --> Q["moment 3: postorder emits"]
    Q --> RET["return to parent"]

Trace: the three depth-first orders are one walk

The walk executed on the 7-node tree, one row per moment (computed by running the recursion and logging each moment). Read only the "preorder" rows and you get 1, 2, 4, 5, 3, 6, 7; only the "inorder" rows give 4, 2, 5, 1, 6, 3, 7; only the "postorder" rows give 4, 5, 2, 6, 7, 3, 1.

#MomentNodeCall stack (root → current)Emitted to
1first visit (pre)11preorder
2first visit (pre)21→2preorder
3first visit (pre)41→2→4preorder
4back from left (in)41→2→4inorder
5back from right (post)41→2→4postorder
6back from left (in)21→2inorder
7first visit (pre)51→2→5preorder
8back from left (in)51→2→5inorder
9back from right (post)51→2→5postorder
10back from right (post)21→2postorder
11back from left (in)11inorder
12first visit (pre)31→3preorder
13first visit (pre)61→3→6preorder
14back from left (in)61→3→6inorder
15back from right (post)61→3→6postorder
16back from left (in)31→3inorder
17first visit (pre)71→3→7preorder
18back from left (in)71→3→7inorder
19back from right (post)71→3→7postorder
20back from right (post)31→3postorder
21back from right (post)11postorder

21 rows = 3 moments × 7 nodes. The call stack never gets deeper than 3 frames, which is the height plus one: that is the space bound made visible.

Recursive Traversals

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


def inorder(root: TreeNode | None) -> list[int]:
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

def preorder(root: TreeNode | None) -> list[int]:
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

def postorder(root: TreeNode | None) -> list[int]:
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]


root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6), TreeNode(7)))
assert inorder(root) == [4, 2, 5, 1, 6, 3, 7]
assert preorder(root) == [1, 2, 4, 5, 3, 6, 7]
assert postorder(root) == [4, 5, 2, 6, 7, 3, 1]
assert inorder(None) == []
print("ok")
import java.util.ArrayList;
import java.util.List;

public class RecursiveTraversals {
    static final class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this(val, null, null); }
        TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
    }

    static void inorder(TreeNode n, List<Integer> out) {
        if (n == null) return;
        inorder(n.left, out);
        out.add(n.val);
        inorder(n.right, out);
    }

    static void preorder(TreeNode n, List<Integer> out) {
        if (n == null) return;
        out.add(n.val);
        preorder(n.left, out);
        preorder(n.right, out);
    }

    static void postorder(TreeNode n, List<Integer> out) {
        if (n == null) return;
        postorder(n.left, out);
        postorder(n.right, out);
        out.add(n.val);
    }

    static void check(boolean cond) { if (!cond) throw new AssertionError(); }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1,
                new TreeNode(2, new TreeNode(4), new TreeNode(5)),
                new TreeNode(3, new TreeNode(6), new TreeNode(7)));
        List<Integer> in = new ArrayList<>(), pre = new ArrayList<>(), post = new ArrayList<>();
        inorder(root, in);
        preorder(root, pre);
        postorder(root, post);
        check(in.equals(List.of(4, 2, 5, 1, 6, 3, 7)));
        check(pre.equals(List.of(1, 2, 4, 5, 3, 6, 7)));
        check(post.equals(List.of(4, 5, 2, 6, 7, 3, 1)));
        System.out.println("ok");
    }
}
#include <cassert>
#include <iostream>
#include <vector>

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

void inorder(const TreeNode* n, std::vector<int>& out) {
    if (!n) return;
    inorder(n->left, out);
    out.push_back(n->val);
    inorder(n->right, out);
}

void preorder(const TreeNode* n, std::vector<int>& out) {
    if (!n) return;
    out.push_back(n->val);
    preorder(n->left, out);
    preorder(n->right, out);
}

void postorder(const TreeNode* n, std::vector<int>& out) {
    if (!n) return;
    postorder(n->left, out);
    postorder(n->right, out);
    out.push_back(n->val);
}

void destroy(TreeNode* n) {
    if (!n) return;
    destroy(n->left);
    destroy(n->right);
    delete n;
}

int main() {
    TreeNode* root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)),
                                  new TreeNode(3, new TreeNode(6), new TreeNode(7)));
    std::vector<int> in, pre, post;
    inorder(root, in);
    preorder(root, pre);
    postorder(root, post);
    assert((in == std::vector<int>{4, 2, 5, 1, 6, 3, 7}));
    assert((pre == std::vector<int>{1, 2, 4, 5, 3, 6, 7}));
    assert((post == std::vector<int>{4, 5, 2, 6, 7, 3, 1}));
    destroy(root);
    std::cout << "ok\n";
}
class TreeNode<T> {
  val: T;
  left: TreeNode<T> | null;
  right: TreeNode<T> | null;
  constructor(val: T, left: TreeNode<T> | null = null, right: TreeNode<T> | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function inorder(root: TreeNode<number> | null, result: number[] = []): number[] {
  if (root === null) return result;
  inorder(root.left, result);
  result.push(root.val);
  inorder(root.right, result);
  return result;
}

function preorder(root: TreeNode<number> | null, result: number[] = []): number[] {
  if (root === null) return result;
  result.push(root.val);
  preorder(root.left, result);
  preorder(root.right, result);
  return result;
}

function postorder(root: TreeNode<number> | null, result: number[] = []): number[] {
  if (root === null) return result;
  postorder(root.left, result);
  postorder(root.right, result);
  result.push(root.val);
  return result;
}

const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3, new TreeNode(6), new TreeNode(7)));
const same = (a: number[], b: number[]) => a.length === b.length && a.every((x, i) => x === b[i]);
if (!same(inorder(root), [4, 2, 5, 1, 6, 3, 7])) throw new Error("inorder");
if (!same(preorder(root), [1, 2, 4, 5, 3, 6, 7])) throw new Error("preorder");
if (!same(postorder(root), [4, 5, 2, 6, 7, 3, 1])) throw new Error("postorder");
console.log("ok");

The Python version is the clearest but not the cheapest: inorder(root.left) + [root.val] + inorder(root.right) builds a new list at every node, and concatenation copies, so on a degenerate (chain-shaped) tree it costs . The TypeScript, Java and C++ versions pass one accumulator down and are on every shape. Use the accumulator style whenever can be large.

Iterative Inorder (using stack)

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


def inorder_iterative(root: TreeNode | None) -> list[int]:
    result = []
    stack = []
    current = root

    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right

    return result


root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6), TreeNode(7)))
assert inorder_iterative(root) == [4, 2, 5, 1, 6, 3, 7]
assert inorder_iterative(None) == []
# A 100,000-node left chain: recursion would overflow CPython's default limit of 1000.
deep = None
for v in range(100_000):
    deep = TreeNode(v, deep)
assert inorder_iterative(deep) == list(range(100_000))
print("ok")
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class IterativeInorder {
    static final class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this(val, null, null); }
        TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
    }

    static List<Integer> inorderIterative(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode current = root;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {          // go as far left as possible
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            result.add(current.val);
            current = current.right;
        }
        return result;
    }

    static void check(boolean cond) { if (!cond) throw new AssertionError(); }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1,
                new TreeNode(2, new TreeNode(4), new TreeNode(5)),
                new TreeNode(3, new TreeNode(6), new TreeNode(7)));
        check(inorderIterative(root).equals(List.of(4, 2, 5, 1, 6, 3, 7)));
        check(inorderIterative(null).isEmpty());
        TreeNode deep = null;
        for (int v = 0; v < 100_000; v++) deep = new TreeNode(v, deep, null);
        List<Integer> d = inorderIterative(deep);
        check(d.size() == 100_000 && d.get(0) == 0 && d.get(99_999) == 99_999);
        System.out.println("ok");
    }
}
#include <cassert>
#include <iostream>
#include <vector>

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

std::vector<int> inorderIterative(TreeNode* root) {
    std::vector<int> result;
    std::vector<TreeNode*> stack;
    TreeNode* current = root;
    while (current || !stack.empty()) {
        while (current) {                       // go as far left as possible
            stack.push_back(current);
            current = current->left;
        }
        current = stack.back();
        stack.pop_back();
        result.push_back(current->val);
        current = current->right;
    }
    return result;
}

void destroyIterative(TreeNode* root) {         // no recursion: safe on deep chains
    std::vector<TreeNode*> st;
    if (root) st.push_back(root);
    while (!st.empty()) {
        TreeNode* n = st.back();
        st.pop_back();
        if (n->left) st.push_back(n->left);
        if (n->right) st.push_back(n->right);
        delete n;
    }
}

int main() {
    TreeNode* root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)),
                                  new TreeNode(3, new TreeNode(6), new TreeNode(7)));
    assert((inorderIterative(root) == std::vector<int>{4, 2, 5, 1, 6, 3, 7}));
    assert(inorderIterative(nullptr).empty());
    TreeNode* deep = nullptr;
    for (int v = 0; v < 100000; v++) deep = new TreeNode(v, deep, nullptr);
    std::vector<int> d = inorderIterative(deep);
    assert(d.size() == 100000 && d.front() == 0 && d.back() == 99999);
    destroyIterative(root);
    destroyIterative(deep);
    std::cout << "ok\n";
}
class TreeNode<T> {
  val: T;
  left: TreeNode<T> | null;
  right: TreeNode<T> | null;
  constructor(val: T, left: TreeNode<T> | null = null, right: TreeNode<T> | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function inorderIterative(root: TreeNode<number> | null): number[] {
  const result: number[] = [];
  const stack: TreeNode<number>[] = [];
  let current = root;

  while (current !== null || stack.length > 0) {
    // Go as far left as possible
    while (current !== null) {
      stack.push(current);
      current = current.left;
    }
    current = stack.pop()!;
    result.push(current.val);
    current = current.right;
  }

  return result;
}

const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3, new TreeNode(6), new TreeNode(7)));
if (inorderIterative(root).join(",") !== "4,2,5,1,6,3,7") throw new Error("inorder");
if (inorderIterative(null).length !== 0) throw new Error("empty");
let deep: TreeNode<number> | null = null;
for (let v = 0; v < 100_000; v++) deep = new TreeNode(v, deep, null);
const d = inorderIterative(deep);
if (d.length !== 100_000 || d[0] !== 0 || d[99_999] !== 99_999) throw new Error("deep");
console.log("ok");

Each test block above ends with a 100,000-node left chain. The recursive versions would hit CPython's default recursion limit of 1000 long before that; the explicit stack does not care about shape.

Trace: iterative inorder on the 7-node tree

Computed by instrumenting the function above. current is the value after the row's action; the stack is shown bottom to top.

StepActioncurrentStack (bottom → top)Output
1push 1, go left2[1][]
2push 2, go left4[1, 2][]
3push 4, go leftnull[1, 2, 4][]
4pop 4, output it, go rightnull[1, 2][4]
5pop 2, output it, go right5[1][4, 2]
6push 5, go leftnull[1, 5][4, 2]
7pop 5, output it, go rightnull[1][4, 2, 5]
8pop 1, output it, go right3[][4, 2, 5, 1]
9push 3, go left6[3][4, 2, 5, 1]
10push 6, go leftnull[3, 6][4, 2, 5, 1]
11pop 6, output it, go rightnull[3][4, 2, 5, 1, 6]
12pop 3, output it, go right7[][4, 2, 5, 1, 6, 3]
13push 7, go leftnull[7][4, 2, 5, 1, 6, 3]
14pop 7, output it, go rightnull[][4, 2, 5, 1, 6, 3, 7]

Exactly 7 pushes and 7 pops: every node enters and leaves the stack once, so the loop is even though it has a nested while. The invariant that makes it correct: the stack always holds, bottom to top, the ancestors of current whose left subtrees are being processed and whose own value has not been output yet — precisely the nodes the recursive version would have suspended at "moment 2".

Level-Order Traversal (BFS)

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


from collections import deque

def level_order(root: TreeNode | None) -> list[list[int]]:
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        level = []

        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(level)

    return result


root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6), TreeNode(7)))
assert level_order(root) == [[1], [2, 3], [4, 5, 6, 7]]
assert level_order(None) == []
assert level_order(TreeNode(1, TreeNode(2), TreeNode(3, None, TreeNode(5)))) == [[1], [2, 3], [5]]
print("ok")
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

public class LevelOrder {
    static final class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this(val, null, null); }
        TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
    }

    static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int levelSize = queue.size();      // freeze the size: this level only
            List<Integer> level = new ArrayList<>(levelSize);
            for (int i = 0; i < levelSize; 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);
            }
            result.add(level);
        }
        return result;
    }

    static void check(boolean cond) { if (!cond) throw new AssertionError(); }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1,
                new TreeNode(2, new TreeNode(4), new TreeNode(5)),
                new TreeNode(3, new TreeNode(6), new TreeNode(7)));
        check(levelOrder(root).equals(List.of(List.of(1), List.of(2, 3), List.of(4, 5, 6, 7))));
        check(levelOrder(null).isEmpty());
        TreeNode t = new TreeNode(1, new TreeNode(2), new TreeNode(3, null, new TreeNode(5)));
        check(levelOrder(t).equals(List.of(List.of(1), List.of(2, 3), List.of(5))));
        System.out.println("ok");
    }
}
#include <cassert>
#include <iostream>
#include <queue>
#include <vector>

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

std::vector<std::vector<int>> levelOrder(TreeNode* root) {
    std::vector<std::vector<int>> result;
    if (!root) return result;
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        const std::size_t levelSize = q.size();   // freeze the size: this level only
        std::vector<int> level;
        level.reserve(levelSize);
        for (std::size_t i = 0; i < levelSize; i++) {
            TreeNode* node = q.front();
            q.pop();
            level.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        result.push_back(std::move(level));
    }
    return result;
}

void destroy(TreeNode* n) {
    if (!n) return;
    destroy(n->left);
    destroy(n->right);
    delete n;
}

int main() {
    TreeNode* root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)),
                                  new TreeNode(3, new TreeNode(6), new TreeNode(7)));
    assert((levelOrder(root) == std::vector<std::vector<int>>{{1}, {2, 3}, {4, 5, 6, 7}}));
    assert(levelOrder(nullptr).empty());
    TreeNode* t = new TreeNode(1, new TreeNode(2), new TreeNode(3, nullptr, new TreeNode(5)));
    assert((levelOrder(t) == std::vector<std::vector<int>>{{1}, {2, 3}, {5}}));
    destroy(root);
    destroy(t);
    std::cout << "ok\n";
}
class TreeNode<T> {
  val: T;
  left: TreeNode<T> | null;
  right: TreeNode<T> | null;
  constructor(val: T, left: TreeNode<T> | null = null, right: TreeNode<T> | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function levelOrder(root: TreeNode<number> | null): number[][] {
  if (root === null) return [];

  const result: number[][] = [];
  const queue: TreeNode<number>[] = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;
    const level: number[] = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(level);
  }

  return result;
}

const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3, new TreeNode(6), new TreeNode(7)));
if (JSON.stringify(levelOrder(root)) !== JSON.stringify([[1], [2, 3], [4, 5, 6, 7]])) throw new Error("levels");
if (levelOrder(null).length !== 0) throw new Error("empty");
const t = new TreeNode(1, new TreeNode(2), new TreeNode(3, null, new TreeNode(5)));
if (JSON.stringify(levelOrder(t)) !== JSON.stringify([[1], [2, 3], [5]])) throw new Error("ragged");
console.log("ok");

Complexity: All traversals are time. Recursive uses stack space where is height. Level-order uses space where is the maximum width.

`Array.prototype.shift` is O(n)

The TypeScript level-order above uses queue.shift(), which in V8 is linear in the array length for large arrays (it moves every element down). On a perfect tree the last level holds about nodes, so the worst case is quadratic. For big trees keep a read index (let head = 0; const node = queue[head++]) or use a ring buffer — see Queues, Deques & Circular Buffers. Python's deque.popleft, Java's ArrayDeque.poll and C++'s std::queue::pop are all .

Trace: level order on the 7-node tree

One row per dequeue, computed by instrumenting the Python version. The level boundary is the frozen level_size: 1, then 2, then 4.

StepDequeueEnqueueQueue after (front → back)Current level
11[2, 3][2, 3][1]
22[4, 5][3, 4, 5][2]
33[6, 7][4, 5, 6, 7][2, 3]
44—[5, 6, 7][4]
55—[6, 7][4, 5]
66—[7][4, 5, 6]
77—[][4, 5, 6, 7]

The queue peaks at 4 entries after step 3 — the width of the last level. On a perfect tree of nodes that is , so BFS can need memory where DFS on the same tree needs only . On a chain it is the reverse: BFS holds one node, DFS holds frames. Choose the traversal whose memory profile matches the shape you expect.

Iterative preorder and postorder

Preorder is the easiest traversal to make iterative: pop a node, emit it, push its right child and then its left child (so the left one is on top and comes out first).

StepPopPush (right first)Stack afterOutput
11[3, 2][3, 2][1]
22[5, 4][3, 5, 4][1, 2]
34—[3, 5][1, 2, 4]
45—[3][1, 2, 4, 5]
53[7, 6][7, 6][1, 2, 4, 5, 3]
66—[7][1, 2, 4, 5, 3, 6]
77—[][1, 2, 4, 5, 3, 6, 7]

Postorder has a neat trick: run "preorder with left and right swapped" (root, right, left) and reverse the output. Root-right-left reversed is left-right-root. It costs an extra list, which is fine almost always; the single-stack postorder that tracks the last visited node is in Binary Trees & Traversals.

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


def preorder_iterative(root):
    out, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return out


def postorder_iterative(root):
    out, stack = [], [root] if root else []
    while stack:                      # root, right, left ...
        node = stack.pop()
        out.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return out[::-1]                  # ... reversed = left, right, root


root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6), TreeNode(7)))
assert preorder_iterative(root) == [1, 2, 4, 5, 3, 6, 7]
assert postorder_iterative(root) == [4, 5, 2, 6, 7, 3, 1]
assert preorder_iterative(None) == postorder_iterative(None) == []
print("ok")

Morris traversal: inorder in O(1) extra space

Every binary tree with nodes has null child pointers (proved below). Morris traversal (J. H. Morris, 1979) borrows them: before descending into a left subtree, it makes the rightmost node of that subtree (the inorder predecessor) point back to the current node, walks the subtree, follows the temporary "thread" back up, and removes it. No stack, no recursion, extra space, and still time because each edge is walked at most a constant number of times (about 3). It temporarily mutates the tree, so it is unsafe with concurrent readers.

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


def morris_inorder(root):
    out, cur = [], root
    while cur:
        if cur.left is None:
            out.append(cur.val)
            cur = cur.right
            continue
        pred = cur.left                      # find inorder predecessor
        while pred.right and pred.right is not cur:
            pred = pred.right
        if pred.right is None:               # first time here: create thread, go left
            pred.right = cur
            cur = cur.left
        else:                                # second time: left subtree done
            pred.right = None                # remove thread (restore the tree)
            out.append(cur.val)
            cur = cur.right
    return out


root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6), TreeNode(7)))
assert morris_inorder(root) == [4, 2, 5, 1, 6, 3, 7]
assert morris_inorder(root) == [4, 2, 5, 1, 6, 3, 7]   # tree restored: second run identical
assert root.left.right.right is None
print("ok")

The traversal ladder

RungExtra spaceHandles deep trees?Mutates tree?When to use
Recursive call stackNo: CPython stops near depth 1000, Java/C++ near tens of thousands of frames by defaultNoInterviews, balanced trees, clarity first
Explicit stack (iterative) heap memoryYesNoProduction, untrusted or skewed input, iterators (next() = one step)
Morris threadingYesTemporarilyMemory-constrained inorder/preorder; rarely needed in practice
BFS (queue)YesNoAnything "by level", shortest root-to-node distance

The explicit-stack version is also how you write a BST iterator with memory and amortized next() — LeetCode 173 asks for exactly that.

Binary Search Tree (BST)

A BST maintains a sorted invariant: for every node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater.

graph TD
    A["8"] --> B["3"]
    A --> C["10"]
    B --> D["1"]
    B --> E["6"]
    C --> F["9"]
    C --> G["14"]
    E --> H["4"]
    E --> I["7"]
    style A fill:#4CAF50,color:#fff

BST Operations

The four implementations below share one test: insert 8, 3, 10, 1, 6, 9, 14, 4, 7 (which builds the tree in the diagram), check the inorder sequence is sorted, search for a present and an absent key, delete 3 (two children, replaced by its successor 4), then delete the root 8 (replaced by 9).

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


def bst_search(root: TreeNode | None, target: int) -> TreeNode | None:
    if not root or root.val == target:
        return root
    return bst_search(root.left, target) if target < root.val else bst_search(root.right, target)

def bst_insert(root: TreeNode | None, val: int) -> TreeNode:
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = bst_insert(root.left, val)
    else:
        root.right = bst_insert(root.right, val)
    return root

def bst_delete(root: TreeNode | None, key: int) -> TreeNode | None:
    if not root:
        return None

    if key < root.val:
        root.left = bst_delete(root.left, key)
    elif key > root.val:
        root.right = bst_delete(root.right, key)
    else:
        if not root.left:
            return root.right
        if not root.right:
            return root.left

        # Find inorder successor
        successor = root.right
        while successor.left:
            successor = successor.left
        root.val = successor.val
        root.right = bst_delete(root.right, successor.val)

    return root


def inorder(n):
    return inorder(n.left) + [n.val] + inorder(n.right) if n else []

root = None
for v in [8, 3, 10, 1, 6, 9, 14, 4, 7]:
    root = bst_insert(root, v)
assert inorder(root) == [1, 3, 4, 6, 7, 8, 9, 10, 14]
assert bst_search(root, 6).val == 6 and bst_search(root, 5) is None
root = bst_delete(root, 3)
assert root.left.val == 4 and inorder(root) == [1, 4, 6, 7, 8, 9, 10, 14]
root = bst_delete(root, 8)
assert root.val == 9 and inorder(root) == [1, 4, 6, 7, 9, 10, 14]
root = bst_delete(root, 100)                       # absent key: no change
assert inorder(root) == [1, 4, 6, 7, 9, 10, 14]
print("ok")
import java.util.ArrayList;
import java.util.List;

public class BstOperations {
    static final class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    static TreeNode search(TreeNode root, int target) {
        while (root != null && root.val != target) root = target < root.val ? root.left : root.right;
        return root;
    }

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

    static TreeNode delete(TreeNode root, int key) {
        if (root == null) return null;
        if (key < root.val) root.left = delete(root.left, key);
        else if (key > root.val) root.right = delete(root.right, key);
        else {
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;
            TreeNode s = root.right;                 // inorder successor
            while (s.left != null) s = s.left;
            root.val = s.val;
            root.right = delete(root.right, s.val);
        }
        return root;
    }

    static void inorder(TreeNode n, List<Integer> out) {
        if (n == null) return;
        inorder(n.left, out);
        out.add(n.val);
        inorder(n.right, out);
    }

    static List<Integer> inorder(TreeNode n) { List<Integer> o = new ArrayList<>(); inorder(n, o); return o; }

    static void check(boolean cond) { if (!cond) throw new AssertionError(); }

    public static void main(String[] args) {
        TreeNode root = null;
        for (int v : new int[] {8, 3, 10, 1, 6, 9, 14, 4, 7}) root = insert(root, v);
        check(inorder(root).equals(List.of(1, 3, 4, 6, 7, 8, 9, 10, 14)));
        check(search(root, 6) != null && search(root, 5) == null);
        root = delete(root, 3);
        check(root.left.val == 4 && inorder(root).equals(List.of(1, 4, 6, 7, 8, 9, 10, 14)));
        root = delete(root, 8);
        check(root.val == 9 && inorder(root).equals(List.of(1, 4, 6, 7, 9, 10, 14)));
        root = delete(root, 100);
        check(inorder(root).equals(List.of(1, 4, 6, 7, 9, 10, 14)));
        System.out.println("ok");
    }
}
#include <cassert>
#include <iostream>
#include <vector>

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

TreeNode* bstSearch(TreeNode* root, int target) {
    while (root && root->val != target) root = target < root->val ? root->left : root->right;
    return root;
}

TreeNode* bstInsert(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    if (val < root->val) root->left = bstInsert(root->left, val);
    else root->right = bstInsert(root->right, val);
    return root;
}

TreeNode* bstDelete(TreeNode* root, int key) {
    if (!root) return nullptr;
    if (key < root->val) root->left = bstDelete(root->left, key);
    else if (key > root->val) root->right = bstDelete(root->right, key);
    else {
        if (!root->left) { TreeNode* r = root->right; delete root; return r; }
        if (!root->right) { TreeNode* l = root->left; delete root; return l; }
        TreeNode* s = root->right;                    // inorder successor
        while (s->left) s = s->left;
        root->val = s->val;
        root->right = bstDelete(root->right, s->val);
    }
    return root;
}

void inorder(const TreeNode* n, std::vector<int>& out) {
    if (!n) return;
    inorder(n->left, out);
    out.push_back(n->val);
    inorder(n->right, out);
}

std::vector<int> inorder(const TreeNode* n) { std::vector<int> o; inorder(n, o); return o; }

void destroy(TreeNode* n) {
    if (!n) return;
    destroy(n->left);
    destroy(n->right);
    delete n;
}

int main() {
    TreeNode* root = nullptr;
    for (int v : {8, 3, 10, 1, 6, 9, 14, 4, 7}) root = bstInsert(root, v);
    assert((inorder(root) == std::vector<int>{1, 3, 4, 6, 7, 8, 9, 10, 14}));
    assert(bstSearch(root, 6) && !bstSearch(root, 5));
    root = bstDelete(root, 3);
    assert(root->left->val == 4);
    assert((inorder(root) == std::vector<int>{1, 4, 6, 7, 8, 9, 10, 14}));
    root = bstDelete(root, 8);
    assert(root->val == 9);
    assert((inorder(root) == std::vector<int>{1, 4, 6, 7, 9, 10, 14}));
    root = bstDelete(root, 100);
    assert((inorder(root) == std::vector<int>{1, 4, 6, 7, 9, 10, 14}));
    destroy(root);
    std::cout << "ok\n";
}
class TreeNode<T> {
  val: T;
  left: TreeNode<T> | null;
  right: TreeNode<T> | null;
  constructor(val: T, left: TreeNode<T> | null = null, right: TreeNode<T> | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function bstSearch(root: TreeNode<number> | null, target: number): TreeNode<number> | null {
  if (root === null || root.val === target) return root;
  return target < root.val
    ? bstSearch(root.left, target)
    : bstSearch(root.right, target);
}

function bstInsert(root: TreeNode<number> | null, val: number): TreeNode<number> {
  if (root === null) return new TreeNode(val);
  if (val < root.val) {
    root.left = bstInsert(root.left, val);
  } else {
    root.right = bstInsert(root.right, val);
  }
  return root;
}

function bstDelete(root: TreeNode<number> | null, key: number): TreeNode<number> | null {
  if (root === null) return null;

  if (key < root.val) {
    root.left = bstDelete(root.left, key);
  } else if (key > root.val) {
    root.right = bstDelete(root.right, key);
  } else {
    // Node found — three cases
    if (!root.left) return root.right;
    if (!root.right) return root.left;

    // Two children: replace with inorder successor
    let successor = root.right;
    while (successor.left) successor = successor.left;
    root.val = successor.val;
    root.right = bstDelete(root.right, successor.val);
  }

  return root;
}

const inorder = (n: TreeNode<number> | null): number[] => (n ? [...inorder(n.left), n.val, ...inorder(n.right)] : []);
let root: TreeNode<number> | null = null;
for (const v of [8, 3, 10, 1, 6, 9, 14, 4, 7]) root = bstInsert(root, v);
if (inorder(root).join(",") !== "1,3,4,6,7,8,9,10,14") throw new Error("insert");
if (bstSearch(root, 6)?.val !== 6 || bstSearch(root, 5) !== null) throw new Error("search");
root = bstDelete(root, 3);
if (root!.left!.val !== 4 || inorder(root).join(",") !== "1,4,6,7,8,9,10,14") throw new Error("delete 3");
root = bstDelete(root, 8);
if (root!.val !== 9 || inorder(root).join(",") !== "1,4,6,7,9,10,14") throw new Error("delete 8");
console.log("ok");
OperationAverageWorst (skewed)
Search
Insert
Delete

"Average" here means over random insertion orders: if the keys arrive in a uniformly random permutation, the expected depth of a node is about and the expected height is (CLRS §12.4). It is not an average over operations on a fixed tree. Insert keys in sorted order — a very common real input — and you get the skewed worst case. That is the whole reason balanced trees exist. Duplicates: the insert above sends equal keys right, so a BST with duplicates satisfies "left < node ≤ right"; decide on one rule and keep search, delete and validation consistent with it. The full treatment, including successor, floor/ceiling and order-statistic augmentation, is in Binary Search Trees.

BST Validation

A common interview question: verify that a tree is a valid BST.

TypeScript:

function isValidBST(
  root: TreeNode<number> | null,
  min = -Infinity,
  max = Infinity
): boolean {
  if (root === null) return true;
  if (root.val <= min || root.val >= max) return false;
  return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
}

Python:

def is_valid_bst(root: TreeNode | None, min_val=float('-inf'), max_val=float('inf')) -> bool:
    if not root:
        return True
    if root.val <= min_val or root.val >= max_val:
        return False
    return (is_valid_bst(root.left, min_val, root.val) and
            is_valid_bst(root.right, root.val, max_val))

WARNING

A common mistake is checking only immediate children (left.val < root.val < right.val). This fails for cases where a deeper node violates the BST property. You must pass down the valid range.

An equivalent check uses the theorem proved below: a binary tree is a BST (with distinct keys) if and only if its inorder sequence is strictly increasing. Do an iterative inorder and compare each value with the previous one; no bounds, no sentinel infinities, and it works for any comparable key type. In Java with int keys, the bounds version must use long or nullable bounds, because a node holding Integer.MIN_VALUE would otherwise be rejected by root.val <= min.

Correctness: the facts every tree algorithm leans on

These six facts are used, usually silently, in almost every lesson of this module. Each proof is short; learn them, because interviewers ask "why?" and because they are how you check your own complexity claims.

1. A tree with nodes has exactly edges

Claim. A connected acyclic graph on vertices has edges.

Proof (induction on ). For there are no edges. For , first show a leaf (a vertex of degree 1) exists: take a longest simple path . The endpoint has as a neighbour. Any other neighbour either lies on the path — giving a cycle — or lies off it — giving a longer path. Both are impossible, so . Remove and its edge. The rest is still connected (no path between two other vertices passed through a degree-1 vertex) and still acyclic, so by the induction hypothesis it has edges. Adding back the one removed edge gives . ∎

For rooted trees there is a one-line version: every node except the root has exactly one edge to its parent, and every edge is some node's parent edge, so edges = . Two useful consequences: a connected graph with edges is a tree, and an acyclic graph with edges is a tree (any two of "connected", "acyclic", " edges" imply the third). That is the check behind LeetCode 261 Graph Valid Tree.

2. There is exactly one simple path between any two nodes

Connectivity gives at least one. If there were two different simple paths from to , follow them from until they first diverge and then until they first meet again; the two segments between those points form a cycle. So exactly one. This is why "the distance between two nodes" and "the path between two nodes" are well defined in a tree, and why the path always goes up from to and then down to .

3. Height bounds:

Claim. A binary tree with nodes has height (in edges) satisfying .

Proof. Level contains at most nodes: level 0 has one node, and each node at level contributes at most two to level . Summing levels :

(The last equality holds for every integer ; it was checked for all up to .) The upper bound: a path from the root down has at most nodes, so at most edges, achieved by a chain. ∎

This is the single most important inequality in the module. Any operation that walks one root-to-leaf path costs , which is somewhere between and depending on shape. Balanced trees (AVL, red-black, treaps in expectation, B-trees) are mechanisms for pinning to the low end. For a -ary tree the same argument gives : with , a B-tree with 3 levels below the root (height 3) can reach leaf entries if every node is full.

4. In a full binary tree, leaves = internal nodes + 1

Let be the number of internal nodes (each with exactly 2 children) and the number of leaves. Count edges two ways: each internal node has 2 child edges, so ; and by fact 1, . Equate: . A tournament bracket with 64 teams therefore has 63 games, and a Huffman tree over 256 symbols has 255 internal nodes.

5. A binary tree with nodes has null child pointers

There are child slots and, by fact 1, of them hold edges. The remaining are null. Morris traversal and threaded binary trees exploit exactly these slots; serialization formats that write null markers (LeetCode's [1,2,null,...]) write up to of them.

6. Inorder traversal of a BST visits keys in sorted order

Claim. If satisfies the BST property (every key in the left subtree of is , every key in the right subtree is ), then inorder is strictly increasing. Conversely, if inorder is strictly increasing, is a BST.

Proof (structural induction). An empty tree gives an empty, trivially sorted sequence. For a tree with root , inorder = inorder, , inorder. By the induction hypothesis inorder and inorder are each sorted. Every key in is and every key in is , so the concatenation is sorted. For the converse: in the inorder sequence every key of appears before and every key of after it, so a strictly increasing sequence forces every key of below and every key of above it, at every node. ∎

The converse is what makes the "inorder plus previous value" validation correct, and the forward direction is why tree sort, the BST iterator and "k-th smallest in a BST" all reduce to an inorder walk.

7. Every traversal is

Each node is entered once by its parent's call (or dequeued once), and each edge is walked once downward and once back up. Work per node is (excluding output), so total work is . Space is the maximum stack depth ( frames) for DFS or the maximum queue length (at most the widest level) for BFS. On a perfect tree, the widest level holds nodes.

Self-Balancing BSTs

AVL Trees

AVL trees maintain a balance factor (height difference between left and right subtrees) of at most 1 for every node. This guarantees height.

Rotations:

graph TD
    subgraph "Left Rotation"
        direction TB
        A1["A"] --> B1["B"]
        A1 --> C1["C"]
        B1 --> D1["D"]
        B1 --> E1["E"]
    end

After left rotation on A (when right-heavy):

graph TD
    subgraph "After Left Rotation"
        direction TB
        C2["C"] --> A2["A"]
        C2 --> F2["..."]
        A2 --> D2["D"]
        A2 --> E2["E"]
    end

Four rotation cases: LL (right rotate), RR (left rotate), LR (left-right rotate), RL (right-left rotate).

Correction: what a left rotation actually does

The two diagrams above lose node B and attach B's children to A, which is not a rotation. A left rotation at A applies when A's right child C is too tall. C moves up to A's position, A becomes C's left child, and C's former left subtree () becomes A's right subtree. A's left subtree () and C's right subtree () stay where they are. The inorder order is unchanged, which is why a rotation preserves the BST property, and only two child pointers change, so it is .

flowchart TB
    subgraph before["Before: right-heavy at A"]
        A3["A"] --> T1a["T1"]
        A3 --> C3["C"]
        C3 --> T2a["T2"]
        C3 --> T3a["T3"]
    end
    subgraph after["After rotateLeft(A)"]
        C4["C"] --> A4["A"]
        C4 --> T3b["T3"]
        A4 --> T1b["T1"]
        A4 --> T2b["T2"]
    end
    before --> after

Why AVL height is : let be the minimum number of nodes in an AVL tree of height . The sparsest such tree has subtrees of heights and , so , a Fibonacci-like recurrence giving roughly, hence . The derivation and all four rotation cases with code are in Balanced BSTs.

Red-Black Trees

Red-Black trees use node coloring (red/black) to maintain approximate balance. They guarantee the longest path is at most twice the shortest path, giving operations.

Properties:

  1. Every node is red or black
  2. Root is black
  3. Every null leaf is black
  4. Red nodes have only black children
  5. All paths from a node to its null descendants have the same number of black nodes

From properties 4 and 5: if every root-to-null path has black nodes, no path has more than nodes (reds cannot be adjacent), and the tree contains at least internal nodes, so (CLRS Lemma 13.1). AVL trees are more rigidly balanced (faster lookups); red-black trees do fewer rotations on update (at most 2 per insert, 3 per delete), which is why most standard libraries chose them.

Production Note

You will almost never implement AVL or Red-Black trees from scratch. They are used internally by:

  • Java TreeMap / TreeSet (Red-Black)
  • C++ std::map / std::set (Red-Black)
  • Database indexes (B-trees, a generalization)

Know the concepts and trade-offs, but focus interview prep on BST operations and traversals.

The C++ standard does not mandate red-black trees, only the complexity guarantees; libstdc++, libc++ and MSVC's STL all happen to use them. B-trees are best thought of as a generalization of 2-3-4 trees, which red-black trees encode in binary form. Randomized and amortized alternatives (treaps, splay trees, skip lists) are in Treaps, Splay Trees & Skip Lists.

Tries

A trie (prefix tree) stores strings character by character, sharing common prefixes. Essential for autocomplete, spell check, and prefix-matching problems.

graph TD
    ROOT["(root)"] --> A["a"]
    ROOT --> B["b"]
    A --> P["p"]
    P --> P2["p"]
    P2 --> L["l"]
    L --> E["e*"]
    A --> R["r"]
    R --> T["t*"]
    B --> A2["t*"]
    style E fill:#4CAF50,color:#fff
    style T fill:#4CAF50,color:#fff
    style A2 fill:#4CAF50,color:#fff

Nodes marked with * indicate end of a word. This trie stores: "apple", "art", "bt".

TypeScript:

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEnd: boolean = false;
}

class Trie {
  private root = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char)!;
    }
    node.isEnd = true;
  }

  search(word: string): boolean {
    const node = this._findNode(word);
    return node !== null && node.isEnd;
  }

  startsWith(prefix: string): boolean {
    return this._findNode(prefix) !== null;
  }

  private _findNode(prefix: string): TrieNode | null {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) return null;
      node = node.children.get(char)!;
    }
    return node;
  }
}

Python:

class TrieNode:
    def __init__(self):
        self.children: dict[str, 'TrieNode'] = {}
        self.is_end: bool = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self._find_node(word)
        return node is not None and node.is_end

    def starts_with(self, prefix: str) -> bool:
        return self._find_node(prefix) is not None

    def _find_node(self, prefix: str) -> TrieNode | None:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node
OperationComplexity
Insert where = word length
Search
Prefix search
Space where = total chars, = alphabet size

The space is for array-of-children nodes (26 pointers per node for lowercase English); the hash-map children used above cost entries but with a hash table's constant overhead per node. A trie's lookup cost depends on the key length, not on how many keys are stored, which is its advantage over a BST of strings ( character comparisons). Compressed (radix/Patricia) tries collapse single-child chains; they are what IP routers and many key-value stores use. Bit tries, XOR problems and longest-prefix match are in Tries in Depth.

Segment Trees

Segment trees answer range queries (sum, min, max) and support point/range updates in time. They are essential for competitive programming and used internally by databases for range operations.

Correction: databases use B+-trees for range queries

Mainstream relational databases answer range predicates (WHERE price BETWEEN 10 AND 20) with B+-tree indexes, not segment trees — see Database Indexing. Segment trees are primarily an in-memory structure for competitive programming and specialised analytics; claiming a general database uses one internally would need a citation, and we do not have one.

graph TD
    A["[0-7] sum=36"] --> B["[0-3] sum=10"]
    A --> C["[4-7] sum=26"]
    B --> D["[0-1] sum=3"]
    B --> E["[2-3] sum=7"]
    C --> F["[4-5] sum=11"]
    C --> G["[6-7] sum=15"]
    D --> H["[0] 1"]
    D --> I["[1] 2"]
    E --> J["[2] 3"]
    E --> K["[3] 4"]
    F --> L["[4] 5"]
    F --> M["[5] 6"]
    G --> N["[6] 7"]
    G --> O["[7] 8"]

Python:

class SegmentTree:
    def __init__(self, nums: list[int]):
        self.n = len(nums)
        self.tree = [0] * (4 * self.n)
        self._build(nums, 1, 0, self.n - 1)

    def _build(self, nums: list[int], node: int, start: int, end: int) -> None:
        if start == end:
            self.tree[node] = nums[start]
            return
        mid = (start + end) // 2
        self._build(nums, 2 * node, start, mid)
        self._build(nums, 2 * node + 1, mid + 1, end)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def update(self, index: int, val: int) -> None:
        self._update(1, 0, self.n - 1, index, val)

    def _update(self, node: int, start: int, end: int, index: int, val: int) -> None:
        if start == end:
            self.tree[node] = val
            return
        mid = (start + end) // 2
        if index <= mid:
            self._update(2 * node, start, mid, index, val)
        else:
            self._update(2 * node + 1, mid + 1, end, index, val)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def query(self, left: int, right: int) -> int:
        return self._query(1, 0, self.n - 1, left, right)

    def _query(self, node: int, start: int, end: int, left: int, right: int) -> int:
        if right < start or end < left:
            return 0  # out of range
        if left <= start and end <= right:
            return self.tree[node]  # fully within range
        mid = (start + end) // 2
        return (self._query(2 * node, start, mid, left, right) +
                self._query(2 * node + 1, mid + 1, end, left, right))
OperationComplexity
Build
Point update
Range query
Space

Why slots: the tree has nodes in the 1-indexed layout, which is below for every . Why a query is : at each depth, at most two nodes are "partially covered" and recursed into (CLRS-style argument in Segment Trees in Depth), so a query touches at most about nodes. Lazy propagation for range updates and custom merge operations are there too.

Fenwick Tree (Binary Indexed Tree)

A simpler alternative for prefix sum queries and point updates. Uses less memory and has smaller constants.

Python:

class FenwickTree:
    def __init__(self, n: int):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, index: int, delta: int) -> None:
        index += 1  # 1-indexed
        while index <= self.n:
            self.tree[index] += delta
            index += index & (-index)  # add lowest set bit

    def prefix_sum(self, index: int) -> int:
        index += 1  # 1-indexed
        total = 0
        while index > 0:
            total += self.tree[index]
            index -= index & (-index)  # remove lowest set bit
        return total

    def range_sum(self, left: int, right: int) -> int:
        return self.prefix_sum(right) - (self.prefix_sum(left - 1) if left > 0 else 0)

A Fenwick tree is a tree only implicitly: node covers the range and its "parent" for updates is . It needs slots versus about for the recursive segment tree, and both loops run at most times. It handles invertible operations (sum, XOR) naturally but not min/max with arbitrary updates. Details in Fenwick Trees; static range-min in is in Sparse Tables.

Common Tree Patterns

Maximum Depth

Python:

def max_depth(root: TreeNode | None) -> int:
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

Lowest Common Ancestor (BST)

Python:

def lca_bst(root: TreeNode | None, p: TreeNode, q: TreeNode) -> TreeNode | None:
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root
    return None

Lowest Common Ancestor (General Binary Tree)

Python:

def lca(root: TreeNode | None, p: TreeNode, q: TreeNode) -> TreeNode | None:
    if not root or root == p or root == q:
        return root
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left and right:
        return root  # p and q are in different subtrees
    return left or right

Diameter of Binary Tree

Python:

def diameter(root: TreeNode | None) -> int:
    result = 0

    def height(node: TreeNode | None) -> int:
        nonlocal result
        if not node:
            return 0
        left_h = height(node.left)
        right_h = height(node.right)
        result = max(result, left_h + right_h)
        return 1 + max(left_h, right_h)

    height(root)
    return result

The four recipes behind these patterns

Almost every binary-tree interview problem is one of four shapes. Recognising the shape is most of the work; the full catalogue with twenty worked problems is Tree Problem Patterns.

  1. Return a value up (bottom-up, postorder). The answer for a node is a function of the answers for its children: height, size, sum, "is balanced", "is a BST" (return min, max, valid). max_depth above is the template. Write the function signature first — "given a subtree, return X" — then trust the recursion.
  2. Pass state down (top-down, preorder). Each node needs information about its ancestors: current depth, path sum so far, the valid (min, max) range for BST validation, the path string. Pass it as an argument; no return value needed beyond the final collection.
  3. Return one thing, record another (global best). The quantity you want spans two branches through a node (diameter, maximum path sum), but a parent can only extend one branch. Return the best single branch and update a global (or a closure variable) with the best two-branch combination. diameter above is the template; Binary Tree Maximum Path Sum is the same code with sums and a max(0, ...) clamp.
  4. Search with early exit. LCA, "path exists with sum", "find node": return a non-null result as soon as you find it and propagate it up. The general LCA above returns the node itself when found and lets the parent decide.

A fifth recipe, rerooting (compute an answer for every node as root in total with two DFS passes), is the standard trick for "sum of distances from every node" problems; it is covered in the patterns lesson.

Complexity summary

Structure / operationTimeExtra spaceNote
Any traversal (DFS or BFS) DFS, BFS
Morris inorderTemporarily rewires pointers
BST search / insert / delete iterative expected for random insertion order, for sorted input
AVL / red-black search, insert, delete worst case amortized rotations per updateAVL , RB
Binary heap push / pop / peek / / —Build in
Trie insert / search new nodes per insertIndependent of number of keys
Segment tree query / update / build / / (about )Lazy propagation keeps range updates at
Fenwick query / update slotsInvertible operations only
B-tree search (fanout ) node reads— comparisons in total

On constants: pointer-based trees pay a likely cache miss per level, so a red-black tree lookup on a million keys does about 20 dependent memory loads, each potentially around 100 ns when it misses all caches. That is why B-trees (one node = one cache line or one disk page, many keys per node) and array-backed heaps routinely beat textbook binary trees in practice, even when the Big-O is the same. See How Computers Work for the memory hierarchy numbers.

Real-world uses

The browser DOM. An HTML document is parsed into a tree of element, text and attribute nodes. document.querySelectorAll walks it in document order, which is a preorder traversal; CSS selector matching and style inheritance propagate values from parents to children (pattern 2, pass state down); layout computes a node's size from its children (pattern 1, postorder). React and similar libraries keep a virtual tree and diff old against new. A general tree edit distance algorithm is roughly , which the React documentation cites as the reason React instead uses an heuristic that compares nodes level by level and uses key props to match children.

File systems. The directory hierarchy is a rooted tree (hard links to files make it a DAG at the leaves; most file systems forbid hard links to directories precisely to keep the directory structure a tree and .. well defined). du is a postorder traversal (a directory's size is the sum of its children's), find is a preorder traversal, and rm -r must be postorder because a directory has to be empty before it can be removed. Inside the file system, the on-disk structures are trees too: btrfs is built on copy-on-write B-trees, XFS uses B+-trees for extents and directories, and ext4 indexes large directories with an "HTree", a fixed-depth hash-keyed tree.

Compilers and interpreters (ASTs). Source code is parsed into an abstract syntax tree. Python exposes it directly (import ast; ast.parse("a + b * c") returns a BinOp whose right operand is another BinOp, which is how operator precedence is represented). Type checking and constant folding are postorder passes (types of children first), code generation for a stack machine is a postorder walk that emits operands before operators, and pretty-printers are preorder or inorder walks. Babel, the TypeScript compiler, ESLint and tree-sitter-based editors are all AST transformers.

B-trees in databases. Every mainstream relational database's default index is a B+-tree: PostgreSQL's nbtree (based on the Lehman–Yao concurrent B-link tree, 1981), InnoDB's clustered primary-key index, SQLite's table and index b-trees. A node is a disk page (8 KB in PostgreSQL, 16 KB in InnoDB by default, 4 KB by default in SQLite), and with a few hundred keys per page the tree is 3 to 4 levels deep for millions to billions of rows, so a point lookup reads 3 to 4 pages, of which the top levels are almost always cached. Height bound fact 3 with in the hundreds is the whole story. See Database Indexing, Storage Engines and How Databases Work.

Routing tables. An IP router forwards each packet to the route with the longest matching prefix of the destination address — a trie problem. Linux's IPv4 forwarding table (fib_trie) is a level-compressed trie (LC-trie, Nilsson and Karlsson, 1999); hardware routers use compressed multibit tries or TCAMs. A full BGP table is around a million IPv4 prefixes (the exact number moves every month), and each lookup has to complete in nanoseconds. See BGP and Network Layer.

More places trees run. Ordered maps in standard libraries (red-black trees in std::map, TreeMap); the Linux kernel's red-black trees for virtual memory areas and the CFS/EEVDF run queue (CPU Scheduling); priority queues for timers and Dijkstra (Heaps); Merkle trees in Git, certificate transparency logs and blockchains (Cryptography for Engineers); Huffman trees in DEFLATE (gzip, PNG); spatial indexes (R-trees in PostGIS, quadtrees for maps — see Spatial Indexing); decision trees and gradient-boosted tree ensembles in machine learning; and the call tree you see in every profiler's flame graph.

Pitfalls & edge cases

  • Empty tree. root is None/null. Every function's first line should handle it, and the answer for an empty tree must be defined (height or 0? sum 0? max path sum undefined?).
  • Single node. Height 0 (or depth 1); diameter 0; it is both root and leaf.
  • Skewed trees and stack overflow. A tree built from sorted input is a chain. CPython's default recursion limit is 1000; JVM threads default to a stack size of around 512 KB–1 MB depending on platform, which overflows somewhere in the tens of thousands of frames. Codeforces and CSES trees with in a line will crash a naive recursive DFS. Use an explicit stack, or raise the limit and run in a thread with a bigger stack.
  • Height convention mix-ups (edges vs nodes); see the warning in the terminology section.
  • Checking only immediate children in BST validation. A node deep in the right subtree must still exceed every ancestor it is right of.
  • Integer sentinels. Using Integer.MIN_VALUE / INT_MIN as "minus infinity" fails when that value is a legal key. Use long, nullable bounds or the inorder check.
  • Duplicates in a BST. Decide "equal goes right" (or left, or count field) and apply it in insert, search, delete and validation alike.
  • Comparing nodes by value instead of identity. In LCA, root == p should compare node identity; two nodes may hold the same value.
  • Mutating while traversing. Deleting nodes or rewiring pointers inside a recursive traversal invalidates the references the recursion still holds. Collect first, mutate after, or use postorder deliberately.
  • Python list concatenation in traversals is on chains; pass an accumulator.
  • Level boundaries in BFS. Read len(queue) once before the inner loop; reading it inside the loop includes children you just added.
  • Free trees as input. An edge list has no root and no left/right. Pick a root, and in DFS skip the parent (or keep a visited set) or you will walk straight back up the edge you came down.
  • Building from traversals needs two of them. Preorder plus inorder (distinct values) determines a binary tree; preorder plus postorder does not (unless the tree is full). There are 5 binary tree shapes with 3 nodes and 14 with 4 (the Catalan numbers), so one sequence alone cannot pin the shape.

Variations

The module covers the main tree families lesson by lesson (see How this module is organised). A few relatives that live elsewhere or later in the course:

  • N-ary trees (children: list). Every algorithm here generalises by replacing "left, right" with "for child in children". The first-child/next-sibling encoding turns any n-ary tree into a binary one.
  • B-trees and B+-trees. Multiway search trees where each node holds between and children; all leaves at the same depth; B+-trees keep records only in linked leaves for fast range scans. Covered in Database Indexing and Storage Engines.
  • Heaps are complete binary trees with a weaker order (parent ≤ children) than a BST; they give fast min/max but no ordered iteration. Heaps & Priority Queues.
  • Tries, radix trees and suffix trees. Tries are in this module; suffix trees and suffix automata are part of Module 4's string algorithms (for now see String Algorithms).
  • Union-find (disjoint set forest). A forest stored as a parent array, with path compression; it belongs with graphs (Module 4) — preview in Advanced Data Structures.
  • Persistent trees. Path copying gives every version of a tree in extra space per update; this is how functional languages' maps and copy-on-write B-trees (btrfs, LMDB) work.
  • Ropes. Balanced trees of string fragments for editors that need fast insert in the middle of large texts.
  • Spanning trees and shortest-path trees are trees produced by graph algorithms (Kruskal, Prim, BFS, Dijkstra) — Graphs.

Practice Problems

ProblemPatternDifficulty
Maximum Depth of Binary TreeRecursionEasy
Invert Binary TreeRecursionEasy
Same TreeRecursionEasy
Validate BSTRange propagationMedium
Binary Tree Level Order TraversalBFSMedium
Lowest Common AncestorRecursionMedium
Serialize and Deserialize Binary TreePreorder + queueHard
Binary Tree Maximum Path SumDFS + global stateHard
Implement TrieTrie constructionMedium
Word Search IITrie + backtrackingHard

Practice ladder

Fifteen problems in order of difficulty. Each line says what the problem teaches in our words; open the link for the real statement. Problems 1–10 cover the overview; 11–15 are the bridge into the deep lessons.

  1. Maximum Depth of Binary Tree (LeetCode 104) — Easy. The "return a value up" template in three lines; also do it with BFS and count levels.
Hint

The depth of an empty tree is 0; otherwise it is one more than the deeper child.

  1. Invert Binary Tree (LeetCode 226) — Easy. Swap children at every node; any traversal order works, which is the lesson.
Hint

Swap left and right, then recurse into both. Try it iteratively with a queue.

  1. Symmetric Tree (LeetCode 101) — Easy. Recursing on two nodes at once (mirror comparison).
Hint

Write mirror(a, b): both null → true; one null → false; else values equal and mirror(a.left, b.right) and mirror(a.right, b.left).

  1. Binary Tree Inorder Traversal (LeetCode 94) — Easy. Do it recursively, with an explicit stack, and with Morris; compare with the traces above.
Hint

The iterative version: push the whole left spine, pop, output, move to the right child, repeat.

  1. Binary Tree Level Order Traversal (LeetCode 102) — Medium. BFS with frozen level sizes; the base for zigzag, right-side view and level averages.
Hint

Read the queue length once at the start of each level.

  1. Diameter of Binary Tree (LeetCode 543) — Easy. Return-one-record-another: return height, record left + right.
Hint

The longest path through a node uses the heights of both children; the parent can only extend one of them.

  1. Validate Binary Search Tree (LeetCode 98) — Medium. Pass (low, high) bounds down, or check that inorder is strictly increasing.
Hint

Node values can be the extreme 32-bit integers; avoid integer sentinels.

  1. Kth Smallest Element in a BST (LeetCode 230) — Medium. Inorder with early exit; the follow-up asks what to store if the tree is modified often.
Hint

Stop the iterative inorder after the k-th pop.

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


def kth_smallest(root, k):
    stack, cur = [], root
    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        k -= 1
        if k == 0:
            return cur.val
        cur = cur.right
    raise ValueError("k is larger than the tree")


bst = TreeNode(5, TreeNode(3, TreeNode(2, TreeNode(1)), TreeNode(4)), TreeNode(6))
assert [kth_smallest(bst, k) for k in range(1, 7)] == [1, 2, 3, 4, 5, 6]
print("ok")

time, space. Follow-up answer: if insertions and deletions are frequent and many k-th queries arrive, augment each node with its subtree size; then k-th smallest is a single descent (an order-statistic tree).

  1. Lowest Common Ancestor of a Binary Tree (LeetCode 236) — Medium. Search with early exit; the node where the two searches meet.
Hint

If both subtrees report a hit, the current node is the answer; if one does, pass it up.

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


def lca(root, p, q):
    if root is None or root is p or root is q:
        return root
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left and right:
        return root
    return left or right


n6, n2, n0, n8, n7, n4 = TreeNode(6), TreeNode(2), TreeNode(0), TreeNode(8), TreeNode(7), TreeNode(4)
n5, n1, n3 = TreeNode(5, n6, n2), TreeNode(1, n0, n8), None
n2.left, n2.right = n7, n4
root = TreeNode(3, n5, n1)
assert lca(root, n5, n1) is root
assert lca(root, n5, n4) is n5      # a node is its own ancestor
assert lca(root, n7, n4) is n2
print("ok")

time, space. For many queries on a static tree, precompute binary-lifting tables for per query (LCA & Binary Lifting).

  1. Binary Tree Right Side View (LeetCode 199) — Medium. Last node of each BFS level, or DFS visiting right first and recording the first node seen at each depth.
Hint
In DFS, `if depth == len(result): result.append(node.val)` with the right child visited first.
  1. Construct Binary Tree from Preorder and Inorder Traversal (LeetCode 105) — Medium. Why two traversals pin down a tree; index maps to make it .
Hint
The first preorder value is the root; its position in inorder splits the left and right subtrees.
Solution
```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right


def build_tree(preorder, inorder):
    pos = {v: i for i, v in enumerate(inorder)}
    it = iter(preorder)

    def build(lo, hi):                 # inorder[lo..hi]
        if lo > hi:
            return None
        v = next(it)
        node = TreeNode(v)
        node.left = build(lo, pos[v] - 1)
        node.right = build(pos[v] + 1, hi)
        return node

    return build(0, len(inorder) - 1)


def pre(n):
    return [n.val] + pre(n.left) + pre(n.right) if n else []

def ino(n):
    return ino(n.left) + [n.val] + ino(n.right) if n else []

t = build_tree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])
assert pre(t) == [3, 9, 20, 15, 7] and ino(t) == [9, 3, 15, 20, 7]
assert t.right.left.val == 15
print("ok")
```

<span class="math" data-tex="O(n)"></span> time with the position map (without it, searching the root in inorder each time is <span class="math" data-tex="O(n^2)"></span> on a skewed tree), <span class="math" data-tex="O(n)"></span> space.
  1. Subordinates (CSES 1674) — Easy/Medium. A general tree given as a parent list; subtree sizes by postorder, iteratively because is up to .
Hint
Do not assume a boss has a smaller id than the employee. Build child lists, compute an explicit DFS order, and accumulate sizes in reverse order.
Solution
```python
def subordinates(n, boss):            # boss[i] is the boss of employee i + 2
    children = [[] for _ in range(n + 1)]
    for emp, b in enumerate(boss, start=2):
        children[b].append(emp)
    order, stack = [], [1]
    while stack:                      # iterative preorder
        v = stack.pop()
        order.append(v)
        stack.extend(children[v])
    size = [1] * (n + 1)
    for v in reversed(order):         # reverse preorder = children before parents
        for c in children[v]:
            size[v] += size[c]
    return [size[v] - 1 for v in range(1, n + 1)]


assert subordinates(5, [1, 1, 2, 3]) == [4, 1, 1, 0, 0]
chain = subordinates(200_000, list(range(1, 200_000)))   # deep chain, no recursion
assert chain[0] == 199_999 and chain[-1] == 0
print("ok")
```

<span class="math" data-tex="O(n)"></span> time and space. The reverse-preorder trick computes any postorder aggregate without recursion.
  1. Tree Diameter (CSES 1131) — Medium. Diameter of a free tree: two BFS passes (farthest node from anywhere, then farthest from that), or the height recipe.
Hint
The node farthest from an arbitrary start is always one endpoint of some diameter.
  1. Serialize and Deserialize Binary Tree (LeetCode 297) — Hard. Preorder with null markers is a complete encoding (fact 5: exactly markers).
Hint
Write `#` for null. To decode, read tokens with an iterator and rebuild in the same preorder.
Solution
```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right


def serialize(root):
    out, stack = [], [root]
    while stack:                       # iterative preorder with null markers
        n = stack.pop()
        if n is None:
            out.append("#")
            continue
        out.append(str(n.val))
        stack.append(n.right)
        stack.append(n.left)
    return ",".join(out)


def deserialize(data):
    tokens = iter(data.split(","))

    def build():
        t = next(tokens)
        if t == "#":
            return None
        node = TreeNode(int(t))
        node.left = build()
        node.right = build()
        return node

    return build()


root = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))
s = serialize(root)
assert s == "1,2,#,#,3,4,#,#,5,#,#"
assert s.count("#") == 5 + 1            # n + 1 null markers
assert serialize(deserialize(s)) == s
assert serialize(None) == "#" and deserialize("#") is None
print("ok")
```

<span class="math" data-tex="O(n)"></span> time and space. The recursive decoder is fine for balanced trees; for adversarial depth, decode with an explicit stack.
  1. Binary Tree Maximum Path Sum (LeetCode 124) — Hard. The diameter recipe with weights and negative values.
Hint
Return the best downward path starting at the node (never negative contributions: clamp children at 0); record node + left + right globally.
Solution
```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right


def max_path_sum(root):
    best = float("-inf")

    def gain(n):
        nonlocal best
        if n is None:
            return 0
        left = max(gain(n.left), 0)
        right = max(gain(n.right), 0)
        best = max(best, n.val + left + right)   # path bending at n
        return n.val + max(left, right)          # path continuing to the parent

    gain(root)
    return best


assert max_path_sum(TreeNode(1, TreeNode(2), TreeNode(3))) == 6
assert max_path_sum(TreeNode(-10, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))) == 42
assert max_path_sum(TreeNode(-3)) == -3                     # all negative: best single node
print("ok")
```

<span class="math" data-tex="O(n)"></span> time, <span class="math" data-tex="O(h)"></span> space. The `best` initial value must be minus infinity, not 0, or an all-negative tree returns the wrong answer.

Interview follow-ups

  • "Your recursive solution crashes on a tree with 10⁵ nodes in a line. Fix it." Convert to an explicit stack (iterative DFS), or for postorder aggregates use the reverse-preorder trick from the Subordinates solution. Raising the recursion limit is a stopgap, not a fix.
  • "Can you do the traversal with O(1) extra memory?" Morris traversal, at the cost of temporarily modifying the tree; or, if nodes have parent pointers, walk using successor logic.
  • "The tree is too big for memory." Use a B-tree on disk: high fanout keeps height at 3–4, so each operation reads a handful of pages. For traversal of a huge serialized tree, stream it: preorder with null markers can be decoded with a stack in one pass.
  • "Many LCA queries on the same tree." Preprocess with binary lifting ( build, query) or Euler tour + sparse table ( query).
  • "The BST receives keys in sorted order." It degenerates to a list; use a balanced tree (AVL, red-black, treap) or build it once from the sorted array by picking middles (, height ).
  • "Find the k-th smallest repeatedly while the tree changes." Augment nodes with subtree sizes (order-statistic tree); every query is .
  • "Is a heap a BST?" No. A heap only orders parent against children; it cannot do ordered iteration or search in less than . A BST orders left against right.
  • "Serialize a general n-ary tree." Preorder with a child count per node, or with an end-of-children marker.
  • "Prove your traversal is O(n)." Each node is pushed and popped once; each edge is walked down once and up once (fact 7).
  • "Concurrency: many readers, occasional writers." Copy-on-write (persistent) trees give readers a consistent snapshot without locks; databases use B-link trees (Lehman–Yao) with right-sibling pointers so readers can recover from concurrent splits.

Further Reading

Course navigation. Previous: Capstone: A Sorting Library With Benchmarks (end of Module 2). Next: Binary Trees & Traversals. Module index: /algorithms/trees/. Course home: DSA: Zero to Mastery.

Related Archon pages. Recursion & Mathematical Induction, Stacks, Queues, Deques & Circular Buffers, Binary Search Mastery, Advanced Data Structures, Storage Engines, Spatial Indexing.

Sources.

  • Knuth, The Art of Computer Programming, Vol. 1, §2.3 (trees, traversal, threaded trees) and Vol. 3, §6.2 (search trees).
  • Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), 4th ed., Ch. 12 (binary search trees, including §12.4 on randomly built BSTs) and Ch. 13 (red-black trees, Lemma 13.1).
  • Sedgewick and Wayne, Algorithms, 4th ed., §3.2 (BSTs) and §3.3 (balanced search trees, 2-3 trees and left-leaning red-black trees).
  • G. M. Adelson-Velsky and E. M. Landis, "An algorithm for the organization of information", 1962 (AVL trees).
  • R. Bayer and E. McCreight, "Organization and maintenance of large ordered indexes", Acta Informatica 1, 1972 (B-trees).
  • L. J. Guibas and R. Sedgewick, "A dichromatic framework for balanced trees", FOCS 1978 (red-black trees).
  • J. H. Morris, "Traversing binary trees simply and cheaply", Information Processing Letters 9(5), 1979.
  • P. L. Lehman and S. B. Yao, "Efficient locking for concurrent operations on B-trees", ACM TODS 6(4), 1981.
  • S. Nilsson and G. Karlsson, "IP-address lookup using LC-tries", IEEE JSAC 17(6), 1999.
  • cp-algorithms.com, "Segment Tree" and "Fenwick Tree" articles.

Try It Yourself

Problem 1: Given the binary tree [3, 9, 20, null, null, 15, 7], find its maximum depth.

Solution

Use recursion: maxDepth(node) = 1 + max(maxDepth(left), maxDepth(right)).

  • maxDepth(3) = 1 + max(maxDepth(9), maxDepth(20))
  • maxDepth(9) = 1 + max(0, 0) = 1
  • maxDepth(20) = 1 + max(maxDepth(15), maxDepth(7)) = 1 + max(1, 1) = 2
  • maxDepth(3) = 1 + max(1, 2) = 3

Problem 2: Verify whether the following BST is valid: root=5, left=1, right=8, right.left=3, right.right=9.

Solution

A BST requires all nodes in the left subtree < root and all nodes in the right subtree > root. Check node 3 (right.left of root 5): it is in the right subtree of 5, so it must be > 5. But 3 < 5. Answer: Not a valid BST. This is why you must propagate valid ranges, not just check immediate children.

Problem 3: Given a BST with nodes [6, 2, 8, 0, 4, 7, 9, 3, 5], find the Lowest Common Ancestor of nodes 2 and 8.

Solution

Starting at root 6:

  • p=2 and q=8 are on different sides of 6 (2 < 6, 8 > 6)
  • When p and q are on opposite sides, the current node is the LCA. Answer: 6

Problem 4: Perform level-order traversal on the tree: root=1, left=2, right=3, left.left=4, left.right=5.

Solution

Use a queue (BFS):

  • Level 0: dequeue 1, enqueue 2, 3 → output: [1]
  • Level 1: dequeue 2 (enqueue 4, 5), dequeue 3 → output: [2, 3]
  • Level 2: dequeue 4, dequeue 5 → output: [4, 5] Answer: [[1], [2, 3], [4, 5]]

Problem 5: Insert the words "cat", "car", "card" into a Trie. How many nodes (excluding root) does the Trie have?

Solution

Build the trie:

  • "cat": root -> c -> a -> t (3 new nodes)
  • "car": root -> c -> a -> r (1 new node, c and a shared)
  • "card": root -> c -> a -> r -> d (1 new node, c, a, r shared) Total nodes excluding root: 5 (c, a, t, r, d)

Problem 6: A full binary tree has 31 internal nodes. How many leaves and how many nodes does it have, and what is the minimum possible height?

Solution

Leaves = internal + 1 = 32; nodes = 63. A binary tree with 63 nodes has height at least , achieved by the perfect tree ().

Quick Quiz

1. What traversal of a BST produces elements in sorted order?

  • a) Preorder
  • b) Inorder
  • c) Postorder
  • d) Level-order
Answer

b) Inorder — Inorder traversal visits left subtree, then root, then right subtree. Since a BST has left < root < right, this produces a sorted sequence.

2. What is the worst-case time complexity for search in an unbalanced BST?

  • a)
  • b)
  • c)
  • d)
Answer

c) — A skewed BST (all nodes form a single chain) degenerates to a linked list, requiring traversal of all nodes in the worst case.

3. How many edges does a tree with nodes have?

  • a)
  • b)
  • c)
  • d)
Answer

b) — A tree is a connected acyclic graph. Every node except the root has exactly one parent edge, giving exactly edges.

4. What data structure does level-order traversal use internally?

  • a) Stack
  • b) Queue
  • c) Heap
  • d) Hash map
Answer

b) Queue — Level-order traversal (BFS) processes nodes level by level using a FIFO queue. Each node's children are enqueued for processing after the current level completes.

5. What is the time complexity of inserting a word of length into a Trie?

  • a)
  • b)
  • c)
  • d)
Answer

c) — Insertion traverses or creates one node per character in the word, doing constant work at each step.

6. A perfect binary tree of height 19 (in edges) is traversed with BFS and with recursive DFS. Roughly how many entries does each hold at its peak?

Answer

The last level has nodes, so the BFS queue peaks around half a million entries. Recursive DFS holds at most frames. On a chain of the same number of nodes (), the situation reverses.