Tree Traversal in C++: When Recursion Overflows

Revised November 2026. This tutorial first appeared in Korean in 2021. We rebuilt both of its C++ programs with Apple clang 21, once with -Wall -Wextra and once with -fsanitize=address,undefined -g. Both compiled with zero warnings and ran with zero sanitizer reports, and their output matched the 2021 article. What needed fixing was the text: it mixed up full and perfect binary trees, skipped level-order traversal, and never mentioned what happens when recursion meets a very deep tree. We measured that last part on an Apple M1 Pro.

This article is for two kinds of readers: people learning trees for the first time, and people whose recursive tree code ran fine in tests and then crashed in production with nothing but "Segmentation fault". The short answer for the second group: a recursive traversal uses one stack frame per level, so its stack use equals the height of the tree, not the number of nodes. In a balanced tree that is tiny. In a degenerate tree (for example, a binary search tree filled from sorted data) the height equals the node count, and in our measurements the default stack ran out somewhere between 40,000 and 260,000 levels depending on build flags.

Tree vocabulary in five minutes

A tree is a hierarchical, non-linear structure: nodes connected by parent–child links, with no cycles. Lists, stacks and queues are a single line of elements; a tree branches. File systems, the HTML DOM, database indexes (B-trees), JSON documents and compiler syntax trees are all trees.

Using the figure above:

• Root: the only node without a parent, here A.
• Parent, child, sibling: A's children are B and C; B and C are siblings.
• Leaf: a node with no children (I, J, K, L). All other nodes are internal nodes.
• Degree: the number of children of a node. A, B and C have degree 2; D has degree 1. The degree of a tree is the maximum over its nodes.
• Depth: the number of edges from the root to a node. A is at depth 0, D at 2, I at 3.
• Height: the number of edges on the longest root-to-leaf path. This tree has height 3.
• Level: some textbooks count levels from 0, others from 1. The 2021 article counted from 1. Check the convention before comparing formulas from two sources; most off-by-one errors in tree exercises come from here.

Trees with any number of children

When a node can have any number of children, a simple representation is left-child, right-sibling: each node stores a pointer to its first child and a pointer to its next sibling.

The 2021 version compiled cleanly, but its default constructor Tree() { } left both pointers uninitialized. The example never called it, so nothing went wrong, but any node created that way would have followed garbage pointers. Default member initializers remove that trap:

#include <cstdio>

struct TreeNode {                     // left child, right sibling
    char data;
    TreeNode* child = nullptr;        // first child
    TreeNode* sibling = nullptr;      // next sibling on the same level
    explicit TreeNode(char d) : data(d) {}

    void append_child(TreeNode* c) {
        if (!child) { child = c; return; }
        TreeNode* t = child;
        while (t->sibling) t = t->sibling;
        t->sibling = c;
    }
    void print(int depth) const {
        std::printf("%*s%c\n", depth, "", data);
        if (child)   child->print(depth + 1);   // one level down
        if (sibling) sibling->print(depth);     // same level
    }
};

int main() {
    TreeNode root('A'), B('B'), C('C'), D('D'), E('E'), F('F');
    root.append_child(&B);
    B.append_child(&C);
    B.append_child(&D);
    root.append_child(&E);
    E.append_child(&F);
    root.print(0);
}

A
 B
  C
  D
 E
  F

Shapes of binary trees: complete, perfect, degenerate

In a binary tree every node has at most two children. A few shapes have names, and the names matter because algorithms rely on them.

A complete binary tree has every level full except possibly the last, and the last level is filled from the left with no gaps (above). Because there are no gaps, it fits in an array without wasted slots, which is exactly why a binary heap uses this shape.

A perfect binary tree has every internal node with two children and every leaf on the same level. With height h it has exactly 2^(h+1) − 1 nodes. Every perfect tree is complete; the reverse is not true.

The 2021 article called this a "Full Binary Tree" and defined it as "every node except the leaves has degree 2". That definition is the usual definition of a full binary tree, which allows leaves at different depths, while the picture showed a perfect tree. Both terms are in common use, so it is worth keeping them apart.

A degenerate (skewed) tree has only one child per node. It is a linked list wearing a tree costume: height equals node count minus one. Inserting already-sorted keys into a plain binary search tree produces exactly this, and it is the shape that kills recursive traversals below.

The four traversals, run for real

The 2021 article covered pre-, in- and post-order and explicitly skipped level order. Here are all four on a nine-node tree: A at the root, B and C below it, D, E, F, G on the next level, and H and I under D.

The red arrows trace the pre-order visit sequence. The 2021 arrow diagrams for in-order and post-order had so many crossing arrows that they were hard to follow, so we replaced them with this summary:

The three depth-first versions are the same function with the printf in a different place. Level order needs a queue instead of recursion:

void preorder(const Node* n)  { if (!n) return; std::printf("%c ", n->data); preorder(n->left); preorder(n->right); }
void inorder(const Node* n)   { if (!n) return; inorder(n->left); std::printf("%c ", n->data); inorder(n->right); }
void postorder(const Node* n) { if (!n) return; postorder(n->left); postorder(n->right); std::printf("%c ", n->data); }

void levelorder(const Node* root) {
    std::queue<const Node*> q;
    if (root) q.push(root);
    while (!q.empty()) {
        const Node* n = q.front(); q.pop();
        std::printf("%c ", n->data);
        if (n->left)  q.push(n->left);
        if (n->right) q.push(n->right);
    }
}

It is easier to remember them by what they are for:

Iterative traversal with an explicit stack

Every recursive call pushes a frame onto the call stack, which is small and fixed in size. The same work can be done with a std::vector used as a stack; it lives on the heap and grows as needed.

void preorder_iter(const Node* root) {
    std::vector<const Node*> st;
    if (root) st.push_back(root);
    while (!st.empty()) {
        const Node* n = st.back(); st.pop_back();
        std::printf("%c ", n->data);
        if (n->right) st.push_back(n->right);   // right first, so left is popped first
        if (n->left)  st.push_back(n->left);
    }
}
void inorder_iter(const Node* root) {
    std::vector<const Node*> st;
    const Node* cur = root;
    while (cur || !st.empty()) {
        while (cur) { st.push_back(cur); cur = cur->left; }
        cur = st.back(); st.pop_back();
        std::printf("%c ", cur->data);
        cur = cur->right;
    }
}
void postorder_iter(const Node* root) {          // two-stack version
    std::vector<const Node*> st, out;
    if (root) st.push_back(root);
    while (!st.empty()) {
        const Node* n = st.back(); st.pop_back();
        out.push_back(n);
        if (n->left)  st.push_back(n->left);
        if (n->right) st.push_back(n->right);
    }
    for (auto it = out.rbegin(); it != out.rend(); ++it) std::printf("%c ", (*it)->data);
}

Real output of the recursive and iterative versions side by side, built with clang++ -std=c++17 -Wall -Wextra (no warnings) and also clean under ASan and UBSan:

pre   (rec):  A B D H I E C F G
pre   (iter): A B D H I E C F G
in    (rec):  H D I B E A F C G
in    (iter): H D I B E A F C G
post  (rec):  H I D E B F G C A
post  (iter): H I D E B F G C A
level:        A B C D E F G H I

The first three orders match the 2021 article character for character; we also re-ran the original 2021 program and got the same three lines.

How deep can recursion go? A measurement

Now the failure case. The test program builds a left-only chain of N nodes (each new node takes the old root as its left child), counts the nodes with a recursive in-order traversal, and frees the chain with a loop:

long count_rec(const Node* n) {                // in-order, recursive
    if (!n) return 0;
    long c = count_rec(n->left);
    c += 1;
    return c + count_rec(n->right);
}
// main: for (i < N) root = new Node{i, root, nullptr};
//       count_rec(root) or count_iter(root);
//       while (root) { Node* next = root->left; delete root; root = next; }

We bisected N until we found the first depth that crashes. ulimit -s reported 8,176 KB, and two complete runs gave identical thresholds.

• -O0: fine up to 174,252 levels; at 174,313 the process died with Segmentation fault and exit code 139. No message, no stack trace.
• -O2: fine up to 261,367 levels. Smaller frames let it go deeper, but optimization does not remove the problem: the call on the right child can become a tail call, the call on the left child cannot.
• ASan + UBSan (-O0): stopped at 40,164 levels. Sanitizer frames are much larger, so it dies earlier, but at least it tells you why:

AddressSanitizer:DEADLYSIGNAL
=================================================================
==64345==ERROR: AddressSanitizer: stack-overflow on address 0x00016f463ff8 (pc 0x0001001a09a0 bp 0x00016f464050 sp 0x00016f463f90 T0)
    #0 0x0001001a09a0 in count_rec(Node const*) depth.cpp
    #1 0x0001001a09cc in count_rec(Node const*) depth.cpp:11
    #2 0x0001001a09cc in count_rec(Node const*) depth.cpp:11

The iterative count_iter in the same binaries printed visited 10000000 nodes for a 10-million-level chain in all three builds.

The destructor recurses too

You can hit the same wall without writing any traversal. If nodes own their children through std::unique_ptr<Node> left, right;, destroying the root destroys its left child, whose destructor destroys its left child, and so on. In an -O2 build that was fine up to 261,367 levels and crashed with exit code 139 beyond that, at the closing brace of main. The crash happened before stdout was flushed, so even the line the program had already "printed" never appeared. For trees that can get deep, free nodes in a loop.

Choosing between recursive and iterative

• Height guaranteed to be O(log n) (red-black trees, heaps, balanced trees): recursion is clearer and perfectly safe. A million nodes means a height of roughly 20 to 40.
• Height depends on input (a plain BST, trees built from user data, parser output): use the iterative form or enforce a depth limit. Remember that secondary threads often have smaller stacks than the main thread; on this Mac pthread_attr_getstacksize reports 512 KB for a new thread, so the limit there would be roughly 16 times lower.
• Debugging an intermittent segfault: run an ASan build first. It names the overflowing function immediately.

Summary

• Level and height conventions differ between textbooks; check whether counting starts at 0 or 1.
• Full (0 or 2 children) and perfect (all leaves on one level) are different; the 2021 article conflated them.
• Pre-, in- and post-order differ only in when the node itself is visited; level order uses a queue. All four were run and their output is shown above.
• Recursive traversal uses stack space proportional to the tree height. On a degenerate tree the 8 MB main-thread stack ran out at about 174,000 levels (-O0), 261,000 (-O2) and 40,000 (ASan). The iterative version handled 10 million.

Adding an ordering rule to a binary tree gives you a binary search tree; adding a shape rule gives you a heap. Searching a sorted array instead of a tree is covered in binary search.