Trees: Fundamentals

Tree vocabulary, the two common representations, all four traversals (recursive and iterative), and the recurring tree-problem patterns: height, diameter, balance, paths and lowest common ancestor.

What you will learn

Tree vocabulary, the two common representations, all four traversals (recursive and iterative), and the recurring tree-problem patterns: height, diameter, balance, paths and lowest common ancestor.

Prerequisites: Modules 7–9 (pointers, stacks, queues) and recursion basics (Module 19 goes deeper).

Terminology

Root, edge, parent, child, sibling, leaf, ancestor, descendant, depth, height, degree, subtree, path, forest, and balanced tree.

Depth of a node: edges from the root to it (root depth 0).

Height of a node: edges on the longest downward path to a leaf (leaf height 0; the empty tree is often given height −1).

A tree with n nodes has exactly n − 1 edges.

Binary tree representations

Pointer-based nodes and array representation for complete trees.

In the array representation (used by heaps, Module 14), the node at index i has children at 2i + 1 and 2i + 2 and its parent at (i − 1) / 2 — no pointers needed, but only compact for complete trees.

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

Traversals

Preorder: root, left, right.

Inorder: left, root, right.

Postorder: left, right, root.

Level order: breadth-first.

Recursive and iterative versions.

Text equivalent: root 1 has children 2 and 3; node 2 has children 4 and 5; node 3 has a left child 6. The program below builds exactly this tree.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

Every traversal visits each node once: O(n) time. Recursive versions use O(h) stack space, where h is the height.

flowchart TD
  A[1] --> B[2]
  A --> C[3]
  B --> D[4]
  B --> E[5]
  C --> F[6]

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

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

void preorder(TreeNode* n, vector<int>& out) { if (!n) return; out.push_back(n->value); preorder(n->left, out); preorder(n->right, out); }
void inorder(TreeNode* n, vector<int>& out) { if (!n) return; inorder(n->left, out); out.push_back(n->value); inorder(n->right, out); }
void postorder(TreeNode* n, vector<int>& out) { if (!n) return; postorder(n->left, out); postorder(n->right, out); out.push_back(n->value); }

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> levels;
    queue<TreeNode*> q;
    if (root) q.push(root);
    while (!q.empty()) {
        levels.emplace_back();
        for (size_t k = q.size(); k > 0; --k) {         // exactly one level per outer iteration
            TreeNode* n = q.front(); q.pop();
            levels.back().push_back(n->value);
            if (n->left) q.push(n->left);
            if (n->right) q.push(n->right);
        }
    }
    return levels;
}
vector<int> inorderIterative(TreeNode* root) {         // explicit stack: no recursion depth
…

preorder : 1 2 4 5 3 6 
inorder  : 4 2 5 1 6 3 
postorder: 4 5 2 6 3 1 
inorder (iterative): 4 2 5 1 6 3 
level order: [1 ] [2 3 ] [4 5 6 ]
height 2, diameter 4 edges, LCA(4,5)=2, LCA(4,6)=1

Tree problem patterns

Height/depth, node count, leaf count, diameter, balance check, path sum, lowest common ancestor, root-to-leaf paths, subtree comparison, serialization/deserialization, and vertical/diagonal traversal.

Most of these follow one shape: compute something from the children's results, combine at the node, possibly update a global answer (the diameter function above returns the height but records the best path through each node). Recognising which value to *return* and which to *record* is the key design decision.

Advanced considerations

Skewed trees can make recursive algorithms O(n) deep and risk stack overflow. Teach iterative alternatives and explicit stack simulation.

A list-shaped tree of 10⁶ nodes needs 10⁶ nested calls with the recursive traversal; with a typical 8 MB stack and ~50–100 bytes per frame that is on the edge of overflow. The iterative inorder above keeps its stack on the heap.

Practice

Easy: count leaves; check whether two trees are identical.

Medium: serialise a binary tree to a string and back (preorder with null markers).

Hard: maximum path sum between any two nodes, where values may be negative.

Quiz

? For the tree 1(2(4,5),3(6)), which traversal printed `4 2 5 1 6 3`?
+ Inorder :: Left subtree, node, right subtree.
- Preorder :: That printed 1 2 4 5 3 6.
- Postorder :: That printed 4 5 2 6 3 1.
- Level order :: That printed [1] [2 3] [4 5 6].

? Why does the diameter function return the height but record the path length separately?
+ The longest path through a node uses both child heights, but a parent can only extend one downward branch. :: Return what the parent needs; record the global answer.
- To save memory. :: No.
- Because diameter equals height. :: Here diameter is 4 edges and height 2.
- It is a bug. :: It is the standard pattern.

? A recursive traversal on a completely skewed tree of n nodes uses how much stack?
+ O(n) :: The height equals n − 1.
- O(log n) :: Only for balanced trees.
- O(1) :: Recursion uses the call stack.
- O(n²) :: No.