Trees: Branching Structures

From a line to a branch

An array, a linked list, a stack, a queue — every structure so far has been linear: each item has at most one item after it. But plenty of real things don't line up. A folder contains several folders, each of which contains more. A company org chart has one boss, then several reports, then their reports. A book splits into chapters, chapters into sections. The shape underneath all of these is a [[tree|tree]]: a node that points to several *children*, each of which is itself the top of a smaller tree.

Notice the twist of fate in computer science: we draw trees upside down. The single starting node sits at the top and is called the root; branches grow *downward* toward the leaves. That's it — a tree is just nodes connected by edges, with one special node on top and no loops anywhere (you can never get back to where you started by following edges downward).

          (1)        <- root
         /   \
      (2)     (3)
      / \       \
   (4) (5)      (6)   <- leaves: 4, 5, 6

  edges go DOWNWARD; 1 is the parent of 2 and 3.

The words you'll need

Trees come with a small family vocabulary, and it's worth nailing down now because every later guide leans on it.

1. Root — the single node at the top, the only one with no parent.
2. Parent / child — if an edge goes from A down to B, A is B's *parent* and B is A's *child*. Every node except the root has exactly one parent.
3. Leaf — a node with no children; the tips of the branches.
4. Depth of a node — how many edges down from the root it sits (the root has depth 0).
5. Height of the tree — the depth of its deepest leaf; how many levels tall the whole thing is.

The binary tree: at most two children

A general tree lets a node have any number of children, but the workhorse of this whole rung is the [[binary-tree|binary tree]]: every node has at most two children, neatly named *left* and *right*. That tidy limit makes binary trees easy to store and, as the next guides show, astonishingly powerful for searching and prioritizing. In C++ a node is just a little struct holding a value and two pointers — and a `nullptr` child simply means "no branch this way."

struct Node {
    int value;
    Node* left  = nullptr;   // child on the left, or nullptr
    Node* right = nullptr;   // child on the right, or nullptr
};

// build a tiny tree:    (1)
//                      /   \
//                   (2)     (3)
Node* root  = new Node{1};
root->left  = new Node{2};
root->right = new Node{3};

Walking the tree with recursion

How do you *visit every node* of a tree? This is where the [[dsa-recursion|recursion]] you learned last rung pays off beautifully. The key insight: a binary tree is *defined* recursively — it's a node, plus a left subtree, plus a right subtree, each of which is itself a binary tree. So the code mirrors the shape exactly. To process a tree, you process the node and recurse into each child; the base case is the empty tree (`nullptr`), where you simply do nothing and return.

The only choice is *when* you handle the node relative to its children. Handle it before the children → *pre-order*. Between left and right → *in-order*. After both children → *post-order*. Same three lines, just reordered — and each order is useful for a different job (in-order, you'll see next guide, reads a search tree out in sorted order).

void inOrder(Node* n) {
    if (n == nullptr) return;     // base case: empty subtree
    inOrder(n->left);             // 1. all of the left subtree
    std::cout << n->value << ' '; // 2. then THIS node
    inOrder(n->right);            // 3. then all of the right subtree
}
// pre-order:  visit node BEFORE the two recursive calls
// post-order: visit node AFTER  the two recursive calls

// for the tree   (2)              in-order  -> 1 2 3
//               /   \             pre-order -> 2 1 3
//            (1)     (3)          post-order-> 1 3 2