Tree Basics

Trees are the recursive structure that shows up whenever a problem has hierarchy, parent-child relationships, or a natural "break it into subproblems" shape. Once you can read that shape, everything from DFS to LCA to tree DP becomes routine.

Difficulty: Beginner · Prereqs: Arrays & Strings, Stack, Queue & Deque

---

Contents

• Intuition
• Trace: a 7-Employee DFS
• Linearizing the Tree: DFS In/Out Times
• When to Reach for This
• C++ STL Reference
• Implementation (Contest-Ready)
• Recursive DFS (Short Version)
• BFS, Diameter, and Is-It-a-Tree
• Reading Rooted-Tree Input
• Operations Reference
• Problem Patterns & Tricks
• Contest Cheat Sheet
• Common Mistakes & Debugging
• Self-Test
• Practice Problems
• Further Reading
• Comprehensive Tree Traversals
• Binary Search Trees

---

Intuition

You have a company with 7 employees. Employee 1 is the CEO. Employees 2 and 3 report to 1. Employees 4 and 5 report to 2. Employees 6 and 7 report to 3. The task is to find all subordinates for any employee, both direct and indirect.

Your data is a flat array of (employee, boss) pairs:

pairs[] = { (2,1), (3,1), (4,2), (5,2), (6,3), (7,3) }

Find everyone under employee 1 by repeatedly scanning the array:

1. Scan all 6 pairs for boss == 1. Found: {2, 3}. 6 comparisons.
2. Scan all 6 pairs for boss == 2. Found: {4, 5}. 6 comparisons.
3. Scan all 6 pairs for boss == 3. Found: {6, 7}. 6 comparisons.
4. Scan all 6 pairs for boss == 4. Found: nothing. 6 comparisons.
5. Scan all 6 pairs for boss == 5. Found: nothing. 6 comparisons.
6. Scan all 6 pairs for boss == 6. Found: nothing. 6 comparisons.
7. Scan all 6 pairs for boss == 7. Found: nothing. 6 comparisons.

Total: 42 comparisons just to list 6 subordinates. Every time we discover a new subordinate, we have to scan the entire array again to find their subordinates. With $n$ employees, the worst case is $O(n^2)$—for each of the $n$ people, scan all $n$ pairs.

The real problem is not the number of employees; it is the representation. A flat array tells us who reports to whom, but it does not tell us how to walk downward through the hierarchy without searching. There has to be a better way.

If each employee stores a direct list of who reports to them, finding all subordinates becomes a single walk down the hierarchy—no scanning, no redundancy.

Think of a file system. When you run ls /home/, you do not scan every file on disk—the directory already knows its children. To list everything under /home/, you walk down from /home/ to its subdirectories, then their subdirectories, and so on. The structure gives you the path instead of forcing you to search for it.

That is exactly what a tree is: each node stores pointers to its children, and traversal means following those pointers instead of repeatedly scanning the input.

Trace: a 7-Employee DFS

Build an adjacency list where children[x] holds the direct reports of x. Read pairs one by one:

Input: (2,1) -> children[1] = {2}
Input: (3,1) -> children[1] = {2, 3}
Input: (4,2) -> children[2] = {4}
Input: (5,2) -> children[2] = {4, 5}
Input: (6,3) -> children[3] = {6}
Input: (7,3) -> children[3] = {6, 7}

Six pairs, six insertions. The tree looks like:

            1
           / \
          2   3
         / \ / \
        4  5 6  7

Find all subordinates of employee 1 via DFS.

Start at node 1. Visit children[1] = {2, 3} and keep walking downward.

Start. Push 1.

  stack: [1]       visited: {}

Pop 1, record it, push its children 2 and 3.

  stack: [3, 2]    visited: {1}

Pop 2, push its children 4 and 5.

  stack: [3, 5, 4] visited: {1, 2}

Process 4 (leaf), then 5 (leaf), then 3.

Pop 4—no children, done. Pop 5—no children, done. Pop 3, push 6 and 7.

  stack: [7, 6]    visited: {1, 2, 4, 5, 3}

Pop 6 (leaf). Pop 7 (leaf). Stack empty.

  stack: []        visited: {1, 2, 4, 5, 3, 6, 7}

Final DFS visit order: 1, 2, 4, 5, 3, 6, 7. Every node is visited exactly once.

Operation count: 7 node visits + 6 edge traversals = 13 operations total.

Compare that with the brute-force scan: 42 comparisons for the same result. With $n={10}^5$ employees, brute force reaches up to ${10}^{10}$ operations, while the tree walk stays around $2\times {10}^5$. That is the difference between TLE and instant.

The Invariant

+------------------------------------------------------------------+
| PROPERTY: A tree with n nodes has exactly n-1 edges.             |
| Every pair of nodes is connected by exactly one simple path.     |
| Equivalently: a tree is a connected acyclic graph.               |
+------------------------------------------------------------------+

For rooted trees, additional invariants hold:

• Every node except the root has exactly one parent.
• depth[root] = 0, and depth[v] = depth[parent[v]] + 1 for every other node.
• The subtree of node $v$ contains exactly subtree_size[v] nodes (including $v$).

Connect back to our example: the tree with 7 nodes has exactly 6 edges, which is the same as the 6 input pairs. The DFS traversed all 7 nodes by following those 6 edges, and each edge was touched exactly twice—once going down and once coming back up. That is why DFS is $O(n)$: it does at most $2(n-1)$ edge traversals.

When we pop node 2, we push children 4 and 5. If node 2 had a cycle back to node 1, we'd push 1 again and loop forever. The acyclic property is what guarantees DFS terminates.

Linearizing the Tree: DFS In/Out Times

One DFS traversal assigns each node a position in a flat array, making the subtree of any node a contiguous range in that array. That single fact unlocks segment trees, BITs, and prefix sums on trees—no new data structure needed, just a different view of the same structure.

    Tree:           1               Flattened DFS order (one array slot per node):
                   / \
                  2    3            index:  0    1    2    3    4    5
                 / \    \           node:  [1]  [2]  [4]  [5]  [3]  [6]
                4   5    6                 \------ subtree(1) --------/
                                                \- subtree(2) -/
                                                                \sub(3)/

    Subtree of node v -> contiguous range [tin[v], tin[v] + size[v] - 1]
    -> Any subtree query becomes a range query on the flat array!

Between any two nodes in a tree there is exactly one simple path, so you never need Dijkstra or BFS-for-shortest-path—just find the path (via LCA or DFS) and sum the edge weights. That is a major simplification, easy to miss if you are used to general graph problems.

A "balanced" tree has depth $\sim \log n$, but a chain (every node has one child) has depth $n$. Any algorithm that does $O(\text{depth})$ work per node is $O(n\log n)$ on balanced trees but $O(n^2)$ on chains. Always ask: what if this tree is a chain?

  Balanced (depth 2):      Chain (depth 6):       Star (depth 1):

        1                       1                       1
       / \                      |                   /|\ |\ \
      2   3                     2                  2 3 4 5 6 7
     / \ / \                    |
    4  5 6  7                   3         Balanced: max depth = O(log n)
                                |         Chain:    max depth = O(n)  <- danger!
                                4         Star:     max depth = O(1)
                                |
                                5
                                |
                                6
                                |
                                7

An unrooted tree is just a connected acyclic graph—no node is special. Rooting it (picking any node as root) gives every edge a direction, parent to child, and enables subtree queries, depth computation, and LCA. Many problems hand you an unrooted tree and let you pick the root. If a problem says "rooted at node 1", the choice is made for you; if it just says "a tree", you make it yourself.

Those structural facts become useful the moment you can spot them in problem statements.

When to Reach for This

Trigger phrases:

• "rooted tree with $n$ nodes" or "$n-1$ edges connecting $n$ nodes"—direct tree problem
• "parent of each node" or "ancestor/descendant"—tree traversal + depth/parent arrays
• "subtree" or "all nodes below"—DFS with subtree sizes
• "path between two nodes"—tree paths, possibly LCA
• "hierarchical structure" or "directory" or "organizational"—model as tree

Three look-alikes that are not tree problems:

• Problem says "$n$ nodes and $m$ edges" where $m\ne n-1$—it's a general graph, not a tree. You need graph algorithms (BFS/DFS on graphs, cycle detection).
• Problem involves "shortest path" between nodes with weighted edges—tree paths are unique so the shortest path is just the path; but if the graph isn't a tree, use Dijkstra.
• Binary heap problems—a heap is stored as an array and conceptually a tree, but you almost never need explicit tree traversal. Use Priority Queue & Heaps.

---

C++ STL Reference

There's no built-in tree container in the STL. You build trees from vectors.

Representation	Declaration	Use Case	Space
Adjacency list	vector<vector<int>> adj(n+1);	General trees, unrooted trees	$O(n)$
Parent array	vector<int> par(n+1, -1);	Rooted trees, upward queries only	$O(n)$
Weighted adj. list	vector<vector<pair<int,long long>>> adj(n+1);	Trees with edge weights	$O(n)$
Binary tree node	struct Node { int val, left, right; };	Explicit binary trees (rare in CP)	$O(n)$

Adjacency list is the default. For an unrooted tree with $n$ nodes and $n-1$ edges:

int n;
cin >> n;
vector<vector<int>> adj(n + 1);
for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);  // undirected: store both directions
}

Implementation (Contest-Ready)

Minimal Contest Template

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int root = 1;
    vector<int> par(n + 1, 0), dep(n + 1, 0), sz(n + 1, 1);
    vector<int> order;

    // Iterative DFS -- computes parent, depth, subtree size, DFS order
    {
        stack<int> st;
        st.push(root);
        par[root] = -1;
        vector<bool> vis(n + 1, false);
        vis[root] = true;
        while (!st.empty()) {
            int u = st.top(); st.pop();
            order.push_back(u);
            for (int v : adj[u]) {
                if (!vis[v]) {
                    vis[v] = true;
                    par[v] = u;
                    dep[v] = dep[u] + 1;
                    st.push(v);
                }
            }
        }
    }
    // Subtree sizes: process nodes in reverse DFS order so every child
    // is processed before its parent. Then accumulate into parent.
    for (int i = (int)order.size() - 1; i >= 1; i--) {
        sz[par[order[i]]] += sz[order[i]];
    }

    for (int i = 1; i <= n; i++)
        cout << "node " << i << ": depth=" << dep[i]
             << " parent=" << par[i] << " subtree_size=" << sz[i] << "\n";
}

Recursive DFS (Short Version)

For $n\le {10}^5$ and a non-chain tree, recursion is shorter and easier to reason about. The if (v != p) guard is the only thing standing between you and infinite recursion.

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> adj;
vector<int> par, dep, sz;

void dfs(int u, int p) {
    par[u] = p;
    sz[u] = 1;
    for (int v : adj[u]) {
        if (v != p) {
            dep[v] = dep[u] + 1;
            dfs(v, u);
            sz[u] += sz[v];
        }
    }
}

int main() {
    int n; cin >> n;
    adj.resize(n + 1);
    par.resize(n + 1);
    dep.resize(n + 1, 0);
    sz.resize(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, -1);
}

BFS, Diameter, and Is-It-a-Tree

BFS gives level-order traversal and distances. The diameter of a tree (longest path) is found with two BFS passes: BFS from any node finds the farthest node; BFS from that node gives the diameter. A graph is a tree iff it has $n-1$ edges and is connected.

// BFS from src—returns distances (dist[v] = -1 if unreachable).
auto bfs = [&](int src) -> vector<int> {
    vector<int> dist(n + 1, -1);
    queue<int> q;
    q.push(src);
    dist[src] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;
};

// Diameter via two BFS passes.
auto diameter = [&]() -> int {
    auto d1 = bfs(1);
    int far1 = max_element(d1.begin() + 1, d1.begin() + n + 1) - d1.begin();
    auto d2 = bfs(far1);
    return *max_element(d2.begin() + 1, d2.begin() + n + 1);
};

// Is the input graph a tree?
auto is_tree = [&](int nodes, int edges) -> bool {
    if (edges != nodes - 1) return false;
    auto d = bfs(1);
    for (int i = 1; i <= nodes; i++)
        if (d[i] == -1) return false;  // disconnected
    return true;
};

Reading Rooted-Tree Input

Some problems give parent-based input: node $i$'s parent is $p_i$ for $i=2\dots n$.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    vector<vector<int>> children(n + 1);
    for (int i = 2; i <= n; i++) {
        int p; cin >> p;
        children[p].push_back(i);
    }
    // children[v] now contains the children of v in the rooted tree.
    // No need for visited array -- just iterate children.
}

Operations Reference

Every basic tree operation runs in linear time, scaling directly with the number of nodes.

Operation	Time	Space	Notes
Build adjacency list	$O(n)$	$O(n)$	Read $n-1$ edges
DFS traversal	$O(n)$	$O(n)$	Stack depth up to $O(n)$
BFS traversal	$O(n)$	$O(n)$	Queue size up to $O(n)$
Compute depth / parent	$O(n)$	$O(n)$	Single DFS or BFS pass
Compute subtree sizes	$O(n)$	$O(n)$	Reverse DFS order
Find diameter	$O(n)$	$O(n)$	Two BFS passes
Check if tree	$O(n)$	$O(n)$	Edge count + connectivity

All operations are $O(n)$—the tree's structure guarantees you touch each node and edge at most a constant number of times, and nothing more.

Problem Patterns & Tricks

Subtree Queries via DFS In/Out Times

Assign tin[v] and tout[v] during DFS. Node $u$ is an ancestor of $v$ iff tin[u] <= tin[v] && tout[v] <= tout[u]. This flattens the tree into an array so you can use segment trees or BITs for subtree sum/update queries.

int timer = 0;
void dfs(int u, int p) {
    tin[u] = timer++;
    for (int v : adj[u]) if (v != p) dfs(v, u);
    tout[u] = timer++;
}

See Euler Tour & LCA. Problems: CF 620E, CF 877E.

Rerooting Technique

Compute $f(v)$ for the tree rooted at $v$, for every node $v$. Naive: re-root and DFS from each node, $O(n^2)$. The rerooting trick computes $f(\text{root})$ once, then propagates to children in a second pass by adjusting the contribution of the subtree being moved. Total: $O(n)$. Typical use: "for each node, sum of distances to all other nodes." Problems: CF 1187E, CF 337D.

Tree DP

Process nodes bottom-up (leaves first). Each node combines answers from its children. Classic example—maximum independent set on a tree:

dp[v][0] = sum of max(dp[child][0], dp[child][1]) for all children
dp[v][1] = val[v] + sum of dp[child][0] for all children

See DP on Trees. Problems: CF 1324F, CSES Tree Matching.

Diameter and Centers

The diameter is the longest path; its midpoint(s) form the center, the node that minimizes the maximum distance to any other. Found via two BFS or via DP tracking the two longest downward paths through each node. Problems: CF 1029F, CSES Tree Diameter.

Centroid Decomposition

The centroid of a tree is a node whose removal splits the tree into components of size $\le n/2$. Recursively finding centroids gives a "centroid tree" of depth $O(\log n)$, used for path queries. Problems: CF 342E, CF 321C.

Binary Lifting for LCA

Precompute up[v][k] = the $2^k$-th ancestor of $v$. Answer LCA queries in $O(\log n)$ after $O(n\log n)$ preprocessing. See Euler Tour & LCA. Problems: CF 519E, CSES Company Queries II.

---

Contest Cheat Sheet

+----------------------------------------------------------------+
| TREE BASICS CHEAT SHEET                                        |
|----------------------------------------------------------------|
| Representation:                                                |
|   vector<vector<int>> adj(n+1);   // adjacency list           |
|   for n-1 edges: adj[u].push_back(v); adj[v].push_back(u);   |
|                                                                |
| When to use:                                                   |
|   - n nodes, n-1 edges (it's a tree)                          |
|   - "subtree", "ancestor", "rooted" in problem statement      |
|   - hierarchical structure, parent-child relationships         |
|                                                                |
| Key operations (all O(n)):                                     |
|   - DFS: use stack or recursion (iterative if n > 10^5)       |
|   - BFS: use queue, gives level-order + distances              |
|   - Diameter: BFS from any node, BFS from farthest             |
|   - Subtree size: reverse DFS order, accumulate into parent    |
|                                                                |
| Quick checks:                                                  |
|   - Tree iff: n-1 edges AND connected                         |
|   - Tree iff: connected AND acyclic                            |
|   - Tree iff: n-1 edges AND acyclic                            |
|                                                                |
| Space: O(n) for everything. No tree operation needs > O(n).    |
+----------------------------------------------------------------+

---

Common Mistakes & Debugging

0-indexed vs 1-indexed nodes. Most CF problems use 1-indexed. If you declare vector<...> adj(n) instead of adj(n+1), you'll get out-of-bounds access. Pick a convention and stick to it.

Forgetting to handle the root. When computing parent arrays, the root has no parent. Initialize par[root] = -1 (or 0, depending on convention). If you forget, par[root] defaults to 0 and sz[0] accumulates garbage.

Stack overflow with recursive DFS. For $n>{10}^5$, recursive DFS can exceed the default stack size (~1-8 MB). Use iterative DFS with an explicit stack. If you must use recursion, increase the stack limit with ulimit -s unlimited locally, but many judges won't allow it.

Directed vs undirected input. If the problem gives "parent of node $i$", edges are directed (parent → child). Don't add both directions. If the problem gives "$n-1$ edges", add both directions to the adjacency list.

Not verifying it's a tree. If the problem says "a graph with $n$ nodes and $n-1$ edges" without guaranteeing connectivity, check connectivity. A disconnected graph with $n-1$ edges is a forest, not a tree.

DFS order depends on adjacency list order. The iterative DFS with a stack processes children in reverse order of how they appear in adj[u] (last pushed = first popped). This rarely matters, but if a problem requires a specific traversal order, be aware.

Forgetting the v != p check in recursive DFS. Without if (v != p), you'll traverse the edge back to the parent and recurse infinitely.

Mental Traps

Trap: "I can compute LCA by walking up parents." Walking both nodes up to the root and comparing takes $O(\text{depth})$ per query. On a balanced tree depth is $\log n$—seems fine. On a chain, depth is $n$, and with $q$ queries you get $O(nq)$, which is $\sim {10}^{10}$ for typical limits. Binary lifting precomputes $2^k$-th ancestors in $O(n\log n)$ and answers each query in $O(\log n)$.

  Naive LCA on a chain (n = 7):        Binary lifting (any tree):

       1                                up[v][0] = parent(v)
       |                                up[v][k] = up[up[v][k-1]][k-1]
       2
       |                                Query LCA(5, 6):
       3                                  Jump 5 up by 2^1=2 -> node 2
       |                                  Jump 6 up by 2^1=2 -> node 2
       4                                  Match! LCA = 2
      / \                                 Total: O(log n) jumps
     5   6    LCA(5, 6)?
              Walk 5 up: 5->4->3->2->1      vs. naive: walk each node to root
              Walk 6 up: 6->4->3->2->1                  compare paths -> O(n)
              Compare from root -> O(n)

Trap: "Tree input is always nice and balanced." Problem setters love degenerate cases. If your solution is $O(n\cdot \text{depth})$, test it mentally on a chain. Many "TLE on test 42" verdicts come from assuming trees are shallow.

  n = 5, same node count, very different behavior:

  Balanced:      Chain:        Star:
      1            1             1
     / \           |           / | \
    2   3          2          2  3  4
   / \             |              \
  4   5            3               5
                   |
                   4          depth = 1
                   |          but root processes
  depth = 2        5          n-1 children
  max path = 4   depth = 4
                  max path = 4

Trap: "I'll just recurse without tracking the parent." In an undirected adjacency list, every neighbor of node v includes its parent. Without the if (v != parent) guard, DFS walks back to the parent and loops forever.

  DFS at node 2 (came from parent 1):

        1  <- parent (SKIP!)          adj[2] = {1, 4, 5}
        |                            for v in adj[2]:
       [2] <- current                   v=1: v == parent -> skip ok
       / \                              v=4: recurse dfs(4, 2) ok
      4   5 <- recurse these            v=5: recurse dfs(5, 2) ok

  Without the parent check:
  dfs(2,-1) -> sees neighbor 1 -> dfs(1,-1) -> sees neighbor 2
  -> dfs(2,-1) -> ... -> infinite recursion -> stack overflow

---

Self-Test

Before moving on, verify you can answer these without looking anything up:

• [ ] Given an unrooted tree of n nodes, how many edges does it have? Why?
• [ ] Write iterative DFS on a tree from memory—including the parent check.
• [ ] Explain why DFS on a tree is $O(n)$, not $O(n^2)$—what guarantees each edge is visited at most twice?
• [ ] Given a tree rooted at node 1, what do tin[v] and subtree_size[v] tell you about the range of v's subtree in the DFS-order array?
• [ ] What is the worst-case depth of a tree with n nodes? Give an example.
• [ ] Why does recursive DFS on a chain of 200,000 nodes crash, and what's the fix?
• [ ] Explain why LCA by "walk both nodes up" is O(n) per query, and how binary lifting improves it to O(log n).

---

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Subordinates	CSES	Easy	Subtree sizes
2	Tree Diameter	CSES	Easy	Two-BFS diameter
3	Tree Distances I	CSES	Easy-Med	Two-BFS: max dist from each node
4	Tree Distances II	CSES	Medium	Rerooting: sum of distances
5	CF 1324F -- Maximum White Subtree	CF	Medium	Rerooting DP
6	CF 1187E -- Tree Painting	CF	Medium	Rerooting
7	Company Queries I	CSES	Medium	Binary lifting
8	CF 620E -- New Year Tree	CF	Medium-Hard	Euler tour + segment tree
9	CF 342E -- Xenia and Tree	CF	Hard	Centroid decomposition
10	ABC 220F -- Distance Sums 2	AtCoder	Medium	Rerooting

---

Further Reading

• cp-algorithms: Tree—DFS on trees
• cp-algorithms: Finding the diameter
• cp-algorithms: Euler tour and LCA

Cross-references in this guidebook:

• Set & Multiset—ordered containers built on balanced BSTs
• Priority Queue & Heaps—heap = implicit tree in array
• Euler Tour & LCA—flattening trees, ancestor queries
• DFS & Tree DFS—deeper DFS patterns
• DP on Trees—dynamic programming on tree structures
• Union-Find / DSU—connectivity and forest merging
• Segment Tree—range queries on Euler-tour arrays
• Data Structure Selection Guide—choosing the right structure
• Practice Ladder: Data Structures

---

Comprehensive Tree Traversals

Each of the four classical traversals is illustrated on the same 6-node tree:

        1
       / \
      2   3
     / \   \
    4   5   6

All examples use this node definition:

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

Node* buildSample() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->right = new Node(6);
    return root;
}

In-Order (Left → Root → Right)

Key insight: In-order traversal on a BST produces elements in sorted ascending order—the ordering invariant of the BST is exactly what in-order exploits. Any time you need "all values in sorted order," this is the traversal.

Recursive implementation:

void inorderRecursive(Node* node, vector<int>& result) {
    if (!node) return;
    inorderRecursive(node->left, result);
    result.push_back(node->val);
    inorderRecursive(node->right, result);
}

Iterative version with an explicit stack: walk left as far as possible pushing each node, then pop, visit, and move right.

vector<int> inorderIterative(Node* root) {
    vector<int> result;
    stack<Node*> stk;
    Node* cur = root;

    while (cur || !stk.empty()) {
        while (cur) {              // push all left children
            stk.push(cur);
            cur = cur->left;
        }
        cur = stk.top(); stk.pop();
        result.push_back(cur->val);
        cur = cur->right;          // now explore right subtree
    }
    return result;
}

Trace on the sample tree:

Sample Tree:
        1
       / \
      2   3
     / \   \
    4   5   6

Step  Action                          cur    Stack (top->)      Output
-------------------------------------------------------------------------
  1   Push left: cur=1               1      [1]               []
  2   Push left: cur=2               2      [1, 2]            []
  3   Push left: cur=4               4      [1, 2, 4]         []
  4   cur=4->left is NULL, stop push  NULL   [1, 2, 4]         []
  5   Pop 4, output 4, cur=4->right   NULL   [1, 2]            [4]
  6   Stack not empty: pop 2         NULL   [1]               [4, 2]
      output 2, cur=2->right=5
  7   Push left: cur=5               5      [1, 5]            [4, 2]
  8   cur=5->left is NULL, stop push  NULL   [1, 5]            [4, 2]
  9   Pop 5, output 5, cur=5->right   NULL   [1]               [4, 2, 5]
 10   Stack not empty: pop 1         NULL   []                [4, 2, 5, 1]
      output 1, cur=1->right=3
 11   Push left: cur=3               3      [3]               [4, 2, 5, 1]
 12   cur=3->left is NULL, stop push  NULL   [3]               [4, 2, 5, 1]
 13   Pop 3, output 3, cur=3->right   6      []                [4, 2, 5, 1, 3]
 14   Push left: cur=6               6      [6]               [4, 2, 5, 1, 3]
 15   cur=6->left is NULL, stop push  NULL   [6]               [4, 2, 5, 1, 3]
 16   Pop 6, output 6, cur=6->right   NULL   []                [4, 2, 5, 1, 3, 6]
 17   cur=NULL, stack empty -> DONE                            [4, 2, 5, 1, 3, 6]

Final in-order: 4, 2, 5, 1, 3, 6

Pre-Order (Root → Left → Right)

Key insight: Pre-order gives the DFS entry order—visit the root before either subtree. The first element in a pre-order sequence is always the root, which makes it natural for serialization (you can reconstruct the tree by replaying inserts in the same order) and for creating a structural copy.

Recursive implementation:

void preorderRecursive(Node* node, vector<int>& result) {
    if (!node) return;
    result.push_back(node->val);
    preorderRecursive(node->left, result);
    preorderRecursive(node->right, result);
}

Iteratively, push right first so left is processed first (LIFO).

vector<int> preorderIterative(Node* root) {
    vector<int> result;
    if (!root) return result;
    stack<Node*> stk;
    stk.push(root);

    while (!stk.empty()) {
        Node* node = stk.top(); stk.pop();
        result.push_back(node->val);
        if (node->right) stk.push(node->right);
        if (node->left)  stk.push(node->left);
    }
    return result;
}

Trace:

Sample Tree:
        1
       / \
      2   3
     / \   \
    4   5   6

Step  Action                             Stack (top->)      Output
----------------------------------------------------------------------
  1   Push root 1                        [1]               []
  2   Pop 1, output 1                    []                [1]
      Push right=3, push left=2          [3, 2]
  3   Pop 2, output 2                    [3]               [1, 2]
      Push right=5, push left=4          [3, 5, 4]
  4   Pop 4, output 4                    [3, 5]            [1, 2, 4]
  5   Pop 5, output 5                    [3]               [1, 2, 4, 5]
  6   Pop 3, output 3                    []                [1, 2, 4, 5, 3]
      Push right=6 (no left child)       [6]
  7   Pop 6, output 6                    []                [1, 2, 4, 5, 3, 6]
      6 has no children
  8   Stack empty -> DONE                                   [1, 2, 4, 5, 3, 6]

Final pre-order: 1, 2, 4, 5, 3, 6

Post-Order (Left → Right → Root)

Key insight: Post-order is the reverse of a modified pre-order (Root → Right → Left). It is used for safe deletion of trees (children are deleted before the parent) and for evaluating expression trees (operands are evaluated before the operator). In competitive programming, post-order computes subtree answers before combining them at the root—bottom-up DP.

Recursive implementation:

void postorderRecursive(Node* node, vector<int>& result) {
    if (!node) return;
    postorderRecursive(node->left, result);
    postorderRecursive(node->right, result);
    result.push_back(node->val);
}

Iterative implementation—two stacks:

The idea: do a modified pre-order (Root → Right → Left) into a second stack, then pop the second stack to get post-order.

vector<int> postorderTwoStacks(Node* root) {
    vector<int> result;
    if (!root) return result;
    stack<Node*> s1, s2;
    s1.push(root);

    while (!s1.empty()) {
        Node* node = s1.top(); s1.pop();
        s2.push(node);
        // Push left first, then right (right will be processed first in s1,
        // meaning it goes into s2 before left -- giving L,R,Root order on pop)
        if (node->left)  s1.push(node->left);
        if (node->right) s1.push(node->right);
    }

    while (!s2.empty()) {
        result.push_back(s2.top()->val);
        s2.pop();
    }
    return result;
}

Iterative implementation—single stack variant:

vector<int> postorderOneStack(Node* root) {
    vector<int> result;
    if (!root) return result;
    stack<Node*> stk;
    stk.push(root);

    while (!stk.empty()) {
        Node* node = stk.top(); stk.pop();
        result.push_back(node->val);
        if (node->left)  stk.push(node->left);
        if (node->right) stk.push(node->right);
    }
    // This gives Root->Right->Left; reverse for Left->Right->Root
    reverse(result.begin(), result.end());
    return result;
}

Full trace (two-stack post-order):

Sample Tree:
        1
       / \
      2   3
     / \   \
    4   5   6

Phase 1: Build s2 (modified pre-order: Root -> Right -> Left into s2)

Step  Action                        s1 (top->)    s2 (top->)
----------------------------------------------------------------
  1   Push root 1 to s1             [1]          []
  2   Pop 1 from s1, push to s2     []           [1]
      Push left=2, push right=3     [2, 3]       [1]
  3   Pop 3 from s1, push to s2     [2]          [1, 3]
      Push right=6 (no left)        [2, 6]       [1, 3]
  4   Pop 6 from s1, push to s2     [2]          [1, 3, 6]
  5   Pop 2 from s1, push to s2     []           [1, 3, 6, 2]
      Push left=4, push right=5     [4, 5]       [1, 3, 6, 2]
  6   Pop 5 from s1, push to s2     [4]          [1, 3, 6, 2, 5]
  7   Pop 4 from s1, push to s2     []           [1, 3, 6, 2, 5, 4]
      4 has no children
  8   s1 empty -> Phase 1 done

Phase 2: Pop all from s2
  s2 pop order: 4, 5, 2, 6, 3, 1

Final post-order: 4, 5, 2, 6, 3, 1

Level-Order (BFS)

Level-order visits all nodes at depth $d$ before any node at depth $d+1$, left to right within each level. That breadth-first property makes it the natural choice for depth computation, shortest-path distances in unweighted trees, and any problem that asks about whole levels at once.

vector<vector<int>> levelOrder(Node* root) {
    vector<vector<int>> result;
    if (!root) return result;
    queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        int levelSize = q.size();       // snapshot so we don't consume newly added
        vector<int> currentLevel;
        for (int i = 0; i < levelSize; i++) {
            Node* node = q.front(); q.pop();
            currentLevel.push_back(node->val);
            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
        result.push_back(currentLevel);
    }
    return result;
}

Trace:

Sample Tree:
        1          <- Level 0
       / \
      2   3        <- Level 1
     / \   \
    4   5   6      <- Level 2

Step  Action                              Queue (front->)       Output
--------------------------------------------------------------------------
  1   Enqueue root 1                      [1]                  []
      -- Level 0 (size=1) --
  2   Dequeue 1, output 1                 []                   [[1]]
      Enqueue left=2, right=3             [2, 3]
      -- Level 1 (size=2) --
  3   Dequeue 2, output 2                 [3]                  [[1], [2 ...]]
      Enqueue left=4, right=5             [3, 4, 5]
  4   Dequeue 3, output 3                 [4, 5]               [[1], [2, 3]]
      Enqueue right=6 (no left)           [4, 5, 6]
      -- Level 2 (size=3) --
  5   Dequeue 4, output 4                 [5, 6]               [[1], [2,3], [4 ...]]
      4 has no children
  6   Dequeue 5, output 5                 [6]                  [[1], [2,3], [4,5 ...]]
      5 has no children
  7   Dequeue 6, output 6                 []                   [[1], [2,3], [4,5,6]]
      6 has no children
  8   Queue empty -> DONE

Final level-order: [[1], [2, 3], [4, 5, 6]]
Flat: 1, 2, 3, 4, 5, 6

Traversal Comparison

Traversal	Order	Data Structure	Time	Space	When to Use
In-order	Left → Root → Right	Stack	$O(n)$	$O(h)$	BST sorted output, validate BST property
Pre-order	Root → Left → Right	Stack	$O(n)$	$O(h)$	Serialization, tree copying, prefix expressions
Post-order	Left → Right → Root	Stack(s)	$O(n)$	$O(h)$	Deletion, expression eval, bottom-up DP
Level-order	Top → Bottom, L → R	Queue	$O(n)$	$O(w)$	Level-wise processing, shortest path, BFS

$h$ = tree height (worst case $n$ for a skewed tree, $\log n$ for a balanced one); $w$ = max width (worst case $\sim n/2$ at a complete tree's bottom level).

Morris Traversal—O(1) Space In-Order

Morris traversal achieves $O(1)$ auxiliary space by temporarily threading right pointers of in-order predecessors back to the current node, eliminating the need for a stack or recursion. The tree is restored to its original structure after the traversal.

Algorithm sketch:

1. If cur->left is NULL: output cur, move to cur->right.
2. Else find the in-order predecessor (rightmost node of left subtree):
   • If predecessor's right is NULL → set it to cur (create thread), move left.
   • If predecessor's right is cur → remove thread, output cur, move right.

vector<int> morrisInorder(Node* root) {
    vector<int> result;
    Node* cur = root;

    while (cur) {
        if (!cur->left) {
            result.push_back(cur->val);
            cur = cur->right;
        } else {
            Node* pred = cur->left;
            while (pred->right && pred->right != cur)
                pred = pred->right;

            if (!pred->right) {
                pred->right = cur;      // create thread
                cur = cur->left;
            } else {
                pred->right = nullptr;  // remove thread, visit cur
                result.push_back(cur->val);
                cur = cur->right;
            }
        }
    }
    return result;
}

Each edge is traversed at most 3 times, giving $O(n)$ time with $O(1)$ auxiliary space. In competitive programming, $O(h)$ stack space is almost always acceptable, so Morris is mostly a curiosity—but it appears in interviews and memory-constrained scenarios.

---

Binary Search Trees

A Binary Search Tree is a binary tree with a single ordering invariant that makes search, insert, and delete all $O(h)$ where $h$ is the height.

The BST Property

For every node in the tree:

• All values in the left subtree are strictly less than the node's value.
• All values in the right subtree are strictly greater than the node's value.

This must hold recursively for every subtree—not just the immediate children.

Valid BST:

            8
           / \
          3   10
         / \    \
        1   6   14
           / \  /
          4  7 13

Check node 6: left=4, right=7, with 4 < 6 < 7, and both 4 and 7 sit in the range (3, 8) imposed by ancestors. Every node passes.

Invalid BST:

            5
           / \
          3   8
         / \
        1   7    <- 7 > 5, but 7 is in the left subtree of 5

Node 7 is in the left subtree of 5, but 7 > 5. The immediate parent check (7 > 3) looks fine—the global property is violated. The classic trap: you must validate against bounds inherited from all ancestors, not just the parent.

Search

Start at the root and go left or right based on comparison.

Searching for key = 6 in the valid BST:

        [8]          8 > 6, go left
        / \
      [3]  10        3 < 6, go right
      / \    \
     1  [6]  14      6 == 6, found
        / \  /
       4  7 13

Three comparisons for a 9-node tree.

Node* search(Node* root, int key) {
    while (root) {
        if (key == root->val) return root;
        root = (key < root->val) ? root->left : root->right;
    }
    return nullptr;
}

Complexity: $O(h)$.

Insert

New values always land at a leaf position. Walk down like search, then attach.

Inserting key = 5, path: 8 → 3 → 6 → 4 → right child.

Before:

            8
           / \
          3   10
         / \    \
        1   6   14
           / \  /
          4  7 13

After:

            8
           / \
          3   10
         / \    \
        1   6   14
           / \  /
          4  7 13
           \
            5

Node* insert(Node* root, int key) {
    if (!root) return new Node(key);
    if (key < root->val)
        root->left = insert(root->left, key);
    else if (key > root->val)
        root->right = insert(root->right, key);
    // key == root->val: duplicate, ignore (or handle as needed)
    return root;
}

Complexity: $O(h)$.

Delete

Three cases depending on how many children the target has.

We work with the valid BST (after inserting 5):

            8
           / \
          3   10
         / \    \
        1   6   14
           / \  /
          4  7 13
           \
            5

Case 1: Delete a leaf node (delete 1)

Node 1 has no children—simply remove it.

            8                     8
           / \                   / \
          3   10      →         3   10
         / \    \                \    \
        1   6   14                6   14
           / \  /                / \  /
          4  7 13               4  7 13
           \                     \
            5                     5

Case 2: Delete a node with one child (delete 14)

Node 14 has one child (13)—splice it out by connecting the parent directly to the child.

            8                     8
           / \                   / \
          3   10      →         3   10
           \    \                \    \
            6   14                6   13
           / \  /                / \
          4  7 13               4  7
           \                     \
            5                     5

Case 3: Delete a node with two children (delete 3)

Node 3 has children (left subtree removed earlier) and 6. Replace node 3 with its in-order successor—the smallest value in the right subtree.

Starting tree (after Cases 1 and 2):

            8
           / \
          3   10
           \    \
            6   13
           / \
          4  7
           \
            5

The in-order successor of 3 is 4 (leftmost node in its right subtree). Copy 4's value into node 3's position, then delete the original 4 (a one-child case, handled recursively).

Result:

            8
           / \
          4   10
           \    \
            6   13
           / \
          5  7

Node* findMin(Node* root) {
    while (root->left) root = root->left;
    return root;
}

Node* erase(Node* root, int key) {
    if (!root) return nullptr;
    if (key < root->val) {
        root->left = erase(root->left, key);
    } else if (key > root->val) {
        root->right = erase(root->right, key);
    } else {
        if (!root->left) {
            Node* tmp = root->right;
            delete root;
            return tmp;
        }
        if (!root->right) {
            Node* tmp = root->left;
            delete root;
            return tmp;
        }
        // Two children: replace value with in-order successor, delete it.
        Node* succ = findMin(root->right);
        root->val = succ->val;
        root->right = erase(root->right, succ->val);
    }
    return root;
}

Complexity: $O(h)$ for all three cases.

Validation

In-order traversal of a valid BST produces a sorted sequence—by definition, left subtree < root < right subtree, recursively. The standard validation approach uses min/max bounds that tighten on each recursive call, and correctly catches the "7 in left subtree of 5" mistake from the invalid example above.

#include <climits>

bool isValidBST(Node* root, long long lo = LLONG_MIN, long long hi = LLONG_MAX) {
    if (!root) return true;
    if (root->val <= lo || root->val >= hi) return false;
    return isValidBST(root->left, lo, root->val) &&
           isValidBST(root->right, root->val, hi);
}

For the left child, the upper bound becomes the parent's value; for the right child, the lower bound becomes the parent's value. Complexity: $O(n)$—visits every node exactly once.

BST operations are $O(h)$. What is $h$?

Balanced BST—7 nodes, height 2:

          4
         / \
        2   6
       / \ / \
      1  3 5  7

Operations: $O(\log n)$.

Degenerate BST—inserting 1, 2, 3, 4, 5 in sorted order:

    1
     \
      2
       \
        3
         \
          4
           \
            5

Height 4 for 5 nodes. Effectively a linked list. Operations: $O(n)$.

Shape	Height	Search / Insert / Delete
Balanced	$O(\log n)$	$O(\log n)$
Degenerate	$O(n)$	$O(n)$

Self-balancing BSTs (AVL trees, red-black trees) guarantee $O(\log n)$ height by rebalancing after insertions and deletions. You almost never implement these from scratch in contests—the STL does it for you.

Connection to std::set and std::map

std::set is a balanced BST (a red-black tree in all major STL implementations). Every set operation is a BST operation:

set operation	BST operation
s.insert(x)	BST insert
s.erase(x)	BST delete
s.find(x)	BST search
s.lower_bound(x)	BST search (first $\ge x$)
Range-for over set	In-order traversal

This is why all set/map operations are $O(\log n)$—they inherit BST guarantees from the balanced tree underneath. See Set & Multiset for contest-ready usage patterns.

When BSTs Matter in CP

Custom BST implementations are rare in competitive programming because std::set and std::map handle most needs. But understanding the BST property is essential for:

• Using set/map effectively—knowing it's a BST explains why iteration is sorted, why lower_bound is $O(\log n)$, and why you can't random-access by index.
• Tree problems that ask about BST properties—"is this tree a valid BST?", "find k-th smallest", "convert sorted array to BST".
• Understanding treaps and augmented BSTs—Cartesian Trees (treaps) combine BST order with heap priority; understanding plain BSTs is the prerequisite.
• Tree DP problems—many DP on Trees problems involve subtree properties that mirror BST reasoning.

---

Next Up: Set & Multiset—ordered containers built on the BSTs we just studied