Week 9: Binary Trees & Traversals

1. Binary Tree Fundamentals

A binary tree is a set of nodes where each node has at most two children, conventionally called left and right. There's no ordering rule yet (that arrives in Week 10 with binary search trees) — this week's tree is just a shape. A node with no children is a leaf; the topmost node is the root; the number of edges on the longest root-to-leaf path is the tree's height.

The node struct mirrors the linked-list node from Week 6, just with two pointers instead of one:

tree_node.cpp

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

//         4
//        / \
//       2   6
//      / \ / \
//     1  3 5  7
TreeNode* buildSampleTree() {
    TreeNode* root = new TreeNode(4);
    root->left = new TreeNode(2);
    root->right = new TreeNode(6);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(3);
    root->right->left = new TreeNode(5);
    root->right->right = new TreeNode(7);
    return root;
}

A tree with n nodes has height as low as O(log n) when it's balanced (each level roughly full before the next starts) or as high as O(n) when it's completely skewed — every node has only one child, making it structurally identical to a linked list. Height is the recurring variable in nearly every tree complexity bound you'll state this week and next.

The base case is always nullptr

Nearly every recursive tree function you write follows Week 8's base-case discipline in the exact same way: if (node == nullptr) return ...; is the base case, and the recursive case processes node and calls itself on node->left and node->right, both of which are strictly "smaller" trees. Once you see this shape once, it applies to nearly every tree problem you'll meet.

2. Inorder & Preorder Traversal

A traversal visits every node exactly once; the three depth-first orders differ only in when a node's own value is recorded relative to its children. Inorder visits left subtree, then the node, then right subtree; preorder visits the node first, then left, then right. Both are three-line recursive functions:

traversals_recursive.cpp

#include <vector>
using namespace std;

void inorder(TreeNode* node, vector<int>& out) {
    if (node == nullptr) return;      // base case
    inorder(node->left, out);
    out.push_back(node->val);
    inorder(node->right, out);
}

void preorder(TreeNode* node, vector<int>& out) {
    if (node == nullptr) return;
    out.push_back(node->val);
    preorder(node->left, out);
    preorder(node->right, out);
}

On the sample tree above, inorder produces 1 2 3 4 5 6 7 — sorted order, which is not a coincidence and becomes the core invariant of binary search trees next week. Preorder produces 4 2 1 3 6 5 7, which is useful whenever you need to reconstruct or copy a tree, since the root always comes before its subtrees.

Both recursive traversals rely on the call stack to remember "come back to the parent after finishing the left subtree." You can make that stack explicit instead of implicit with a std::stack, which is worth knowing since interviewers sometimes specifically ask for the iterative version:

inorder_iterative.cpp

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

vector<int> inorderIterative(TreeNode* root) {
    vector<int> out;
    stack<TreeNode*> st;
    TreeNode* curr = root;

    while (curr != nullptr || !st.empty()) {
        while (curr != nullptr) {       // walk all the way left, stacking as we go
            st.push(curr);
            curr = curr->left;
        }
        curr = st.top(); st.pop();      // leftmost unvisited node
        out.push_back(curr->val);
        curr = curr->right;             // then explore its right subtree
    }
    return out;
}

Both directions run in O(n) time since every node is visited once, and O(h) space — h being the tree height — since the stack (or call stack) never holds more than one root-to-current path at a time.

3. Postorder Traversal

Postorder visits both children before the node itself — left, right, then node. It's the order you want whenever a node's processing depends on results already computed for its subtrees, such as deleting a tree (free children before the parent that points to them) or computing an aggregate like height or diameter (Week 10):

postorder_recursive.cpp

void postorder(TreeNode* node, vector<int>& out) {
    if (node == nullptr) return;
    postorder(node->left, out);
    postorder(node->right, out);
    out.push_back(node->val);
}

The iterative version is the trickiest of the three, because postorder needs to visit a node after both children, which doesn't map as directly onto a single stack pop as inorder does. A neat trick sidesteps that: run a "root, right, left" traversal (a mirrored preorder) with a stack, then reverse the output to get "left, right, root":

postorder_iterative.cpp

#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> postorderIterative(TreeNode* root) {
    if (root == nullptr) return {};

    vector<int> out;
    stack<TreeNode*> st;
    st.push(root);

    while (!st.empty()) {
        TreeNode* node = st.top(); st.pop();
        out.push_back(node->val);             // records root, right, left order
        if (node->left)  st.push(node->left);
        if (node->right) st.push(node->right);
    }

    reverse(out.begin(), out.end());           // reversed -> left, right, root
    return out;
}

Postorder is the safe order for deleting a tree

If you manually delete nodes to free memory, do it in postorder — delete both children first, then the current node. Deleting a node before its children means you lose the pointers you'd need to reach and free them, leaking memory or crashing on a dangling access.

4. Level-Order Traversal (BFS with a Queue)

The three orders above are all depth-first — they plunge down one branch before backtracking. Level-order traversal instead visits nodes breadth-first: the root, then every node at depth 1, then every node at depth 2, and so on. This is the same breadth-first idea you used with std::deque in Week 7, implemented here with a plain std::queue:

level_order.cpp

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

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> levels;
    if (root == nullptr) return levels;

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int levelSize = q.size();       // snapshot: exactly this many nodes are on the current level
        vector<int> level;

        for (int 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);
        }
        levels.push_back(level);
    }
    return levels;
}

Taking a snapshot of q.size() before the inner loop is the key trick — it lets you process exactly the current level's nodes without accidentally including children that get pushed during this same pass. Time complexity is O(n), since every node is pushed and popped once; space complexity is O(n) in the worst case, since a wide tree's widest level can hold close to n/2 nodes simultaneously in the queue.

Queue for breadth, stack for depth

This pairing is worth memorizing: a queue (FIFO) naturally processes nodes in the order they were discovered, which is what "level by level" requires; a stack (LIFO) naturally dives into whatever was most recently discovered, which is what depth-first traversal requires. The exact same distinction reappears for graph BFS vs. DFS in Week 12.

5. Hands-on Exercise

Hands-on

Build a tree utility that runs and cross-checks all four traversals

Wire together this week's node struct, all four traversal orders, and a recursive depth calculation into one small program.

Requirements:

Reuse the TreeNode struct and buildSampleTree() from Section 1.
Implement int maxDepth(TreeNode* root) recursively (base case nullptr returns 0; otherwise 1 + max(maxDepth(left), maxDepth(right))).
Implement all four traversals: recursive inorder, recursive preorder, recursive postorder, and iterative level-order.
Print each traversal's output on its own line, labeled, and confirm the inorder result comes out sorted for the sample tree.
Write void freeTree(TreeNode* node) that deletes every node in postorder, and explain in a comment why postorder is the only one of the three depth-first orders that's safe for this.
Extend maxDepth's pattern to write int countNodes(TreeNode* root), counting total nodes with the same recursive shape.

Hint

maxDepth and countNodes are both instances of the same recursive shape: base case nullptr returns an identity value (0), then combine the recursive results from left and right with the node's own contribution. Once you see that template, most simple tree problems become filling in the combine step.

6. Knowledge Check

Four quick questions. Expand each to check your answer.

Why does every recursive tree function check `node == nullptr` as its base case, and how does this connect to Week 8's base-case discipline?

A binary tree is defined recursively — a tree is either empty (nullptr) or a node with two smaller trees as children — so nullptr is the natural point where recursion stops needing to go further. Every recursive call passes node->left or node->right, which are guaranteed to be strictly smaller subtrees, so the calls are guaranteed to eventually reach a nullptr and terminate, satisfying exactly the "reachable base case" requirement from Week 8.

What distinguishes preorder, inorder, and postorder, and give one practical use for each.

They differ only in when the current node's value is recorded relative to its two children: preorder records it before recursing into either child (useful for copying or serializing a tree, since the root always appears before its subtrees), inorder records it between the left and right recursive calls (useful for binary search trees, since it yields values in sorted order), and postorder records it after both children (useful for deleting a tree or computing aggregates like height, since a node's own computation can depend on results already available from both subtrees).

Why does iterative inorder traversal need an explicit stack, while level-order traversal needs a queue instead?

Inorder is depth-first — it needs to remember "return to this ancestor after finishing its left subtree," and a stack's last-in-first-out order naturally resumes the most recently deferred ancestor first, which is exactly the order recursion's own call stack would use. Level-order is breadth-first — it needs to process nodes in the order they were discovered so an entire level finishes before the next one starts, and a queue's first-in-first-out order preserves discovery order directly.

What is the space complexity of a recursive traversal in terms of tree height `h`, and how does it differ between a balanced tree and a fully skewed one?

A recursive traversal's space cost is O(h), since the call stack only ever holds frames for the single root-to-current-node path being explored, not the whole tree. For a balanced tree with n nodes, h is O(log n), so the traversal uses logarithmic extra space; for a completely skewed tree — structurally a linked list — h is O(n), so the same traversal uses linear extra space and can risk a stack overflow on very large inputs.