5 Common Mistakes with Recursion in Tree Traversal

Recursion and tree traversal go together like loops and arrays. It’s a natural fit, but that doesn’t make it foolproof. I’ve seen countless engineers—including myself—trip over the same subtle pitfalls. Whether you’re writing a preorder traversal for a binary search tree or building a recursive crawl of a file system, these five mistakes show up again and again. Let’s break them down so you can spot them before they bite.

1. Missing or Incorrect Base Case

The base case is the exit condition that stops recursion. Without one, your function calls itself infinitely until the stack overflows. It sounds obvious, but I’ve lost count of how many times I’ve seen a recursive tree traversal where the base case checks for null but forgets to return a meaningful value.

Consider a simple inorder traversal that prints node values:

void inorder(Node* root) {
    if (root == nullptr) return;
    inorder(root->left);
    cout << root->value;
    inorder(root->right);
}

The base case here is if (root == nullptr) return;. It works because it prevents recursion on a null child. But what if you accidentally check root != nullptr and forget to recurse? Or what if you mix up nullptr with a sentinel value? A common mistake is to write something like:

void badInorder(Node* root) {
    if (root) {
        badInorder(root->left);
        cout << root->value;
        badInorder(root->right);
    }
    // Missing return for null case? Actually this is fine because the function does nothing.
}

Wait—that’s actually correct! The issue is when you don’t have that if guard, or when you recurse into children without checking for null. Always verify your base case handles null cleanly.

Another classic gotcha: forgetting to return a value from a recursive function that should return something. For example, a function that counts nodes:

int countNodes(Node* root) {
    if (root == nullptr) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

If you omit the base case or return something other than 0, the recursion never sums correctly. Always double-check that your base case returns the right neutral element.

2. Wrong Order of Traversal (Preorder vs Inorder vs Postorder)

Each traversal order has a specific sequence: visit root, left, right for preorder; left, root, right for inorder; left, right, root for postorder. It’s easy to swap them, especially when you’re in a hurry. I once spent an hour debugging a BST validation because my inorder traversal printed values in preorder order—the recursive calls were in the wrong place.

Here’s a quick reference:

Traversal	Order (Root, Left, Right)	Typical Use
Preorder	Root, Left, Right	Copying the tree, prefix notation
Inorder	Left, Root, Right	BST sorted order
Postorder	Left, Right, Root	Deleting tree, postfix notation

A telltale sign of a traversal order mistake is incorrect output. For a BST, an inorder traversal should produce sorted values. If you get unsorted output, check your recursion order. For example, a postorder traversal of a BST will not be sorted.

How to fix it: mentally trace a small tree with three nodes. Write down what order you expect, then run through your code step by step. Or better, use a debugger and watch the call stack.

3. Modifying Shared State or Global Variables

Recursion and shared state are a dangerous combination. When you use a global or class-level variable to accumulate results, each recursive call can overwrite or corrupt the state. For example, building a list of paths in a tree traversal:

vector<int> path; // global
void dfs(Node* root) {
    if (!root) return;
    path.push_back(root->val);
    dfs(root->left);
    dfs(root->right);
    path.pop_back(); // backtrack
}

This code is fragile because the path variable is shared across all recursive calls. If you forget to pop after the right child, the path gets corrupted. A safer approach is to pass the path by value or make a copy, though that may be less efficient.

A better design: pass state explicitly as parameters or use an accumulator pattern:

void dfs(Node* root, vector<int>& path) {
    if (!root) return;
    path.push_back(root->val);
    dfs(root->left, path);
    dfs(root->right, path);
    path.pop_back();
}

Still, the popping is necessary. For strictly functional recursion, prefer returning a result rather than mutating state. For instance, to collect all values:

vector<int> inorderValues(Node* root) {
    if (!root) return {};
    auto left = inorderValues(root->left);
    left.push_back(root->val);
    auto right = inorderValues(root->right);
    left.insert(left.end(), right.begin(), right.end());
    return left;
}

This avoids global state entirely, though it creates intermediate vectors. Choose based on performance needs.

4. Ignoring Recursion Depth and Stack Overflows

Every recursive call adds a stack frame, and there’s a limit. On many systems, the call stack can handle around 1,000 to 10,000 frames depending on the environment. For a balanced binary tree with 1 million nodes, the recursion depth is about log2(1,000,000) ≈ 20, which is fine. But for a skewed tree—like a linked list where each node has only one child—the depth equals the number of nodes. That’s 1,000,000 frames, and you’ll hit a stack overflow quickly.

I once had a production incident where a tree traversal crashed on a deeply nested JSON structure. The fix was to switch to an iterative approach using an explicit stack. For example, iterative inorder traversal:

void iterativeInorder(Node* root) {
    stack<Node*> s;
    Node* curr = root;
    while (curr || !s.empty()) {
        while (curr) {
            s.push(curr);
            curr = curr->left;
        }
        curr = s.top(); s.pop();
        cout << curr->value;
        curr = curr->right;
    }
}

If you must use recursion, consider tail recursion optimization, but not all languages support it. Alternatively, implement a depth-first search with an explicit stack that can grow as needed.

Also, be mindful of recursion in production environments where stack size may be limited. When in doubt, measure the tree height or set a safety check.

5. Not Returning or Using the Recursive Result Correctly

Many recursive functions are written to return a value, but developers sometimes ignore or misuse that return. For example, a function to check if a value exists in a BST might look like:

bool search(Node* root, int target) {
    if (!root) return false;
    if (root->val == target) return true;
    if (target < root->val) search(root->left, target);
    else search(root->right, target);
}

This is wrong! The recursive calls to search return a boolean, but we don’t return that value up the call chain. The function returns true only if the root itself matches. Otherwise, it falls off without a return statement (which is undefined behavior in C++). The correct version is:

bool search(Node* root, int target) {
    if (!root) return false;
    if (root->val == target) return true;
    if (target < root->val) return search(root->left, target);
    else return search(root->right, target);
}

This mistake is incredibly common in interviews. The fix is to always return the result of the recursive call when the function is supposed to propagate a return value.

Another variant: accumulating a result across multiple recursive branches but forgetting to use the returned value. For instance, summing all values in a tree:

int sumTree(Node* root) {
    if (!root) return 0;
    int left = sumTree(root->left);
    int right = sumTree(root->right);
    // Oops: forgot to add root->val
    return left + right;
}

Always ensure you combine the recursive results with the current node’s contribution.

Putting It All Together

Recursion is a powerful tool for tree traversal, but it demands discipline. Check your base case, confirm your traversal order, avoid shared mutable state, watch out for stack depth, and always return values correctly. These five mistakes account for the vast majority of recursive tree traversal bugs I’ve seen. The next time you write a recursive traversal, run through this mental checklist. Your future self—and your code reviewers—will thank you.

If you’re working with more complex tree structures, you might also find value in understanding how tries work. Check out How to Implement a Trie for Autocomplete: A Practical Guide for another angle on recursive tree structures. And when deciding between trees and other data structures, Hash Table vs. Binary Search Tree: When to Use Each can help clarify the trade-offs.

Frequently asked questions

What is recursion in tree traversal?

Recursion in tree traversal is a technique where a function calls itself to visit every node in a tree. The function processes the current node and then recursively visits its child nodes according to a specific order such as preorder, inorder, or postorder.

How do I avoid infinite recursion in tree traversal?

Always include a base case that stops the recursion when the node is null or when a leaf is reached. Ensure that every recursive path eventually reaches the base case. Also, verify that you are not accidentally bypassing the base case due to incorrect conditions.

What is the difference between preorder, inorder, and postorder traversal?

Preorder visits the root first, then left subtree, then right. Inorder visits left, root, then right. Postorder visits left, right, then root. The order matters for different applications: inorder gives sorted order in BSTs, preorder copies trees, postorder deletes trees.

Can recursion cause a stack overflow in tree traversal?

Yes. On deeply skewed trees, recursion depth equals the number of nodes, which can exceed the call stack limit. This causes a stack overflow. To avoid it, use an iterative approach or ensure tree is balanced.

How do I debug recursion in tree traversal?

Use a debugger to step through recursive calls and watch the call stack. Print statements at entry and exit can help trace execution. Start with a small known tree (e.g., three nodes) to verify traversal order and base case behavior.

What happens if I forget the return statement in a recursive function?

If the function is expected to return a value, forgetting the return statement leads to undefined behavior in C/C++ or returning None in Python. The recursive result is lost, and the function may return garbage. Always ensure every path returns a value.

Should I use global variables in recursive tree traversal?

Avoid global or shared mutable state if possible. They make the code harder to reason about and prone to bugs from unintended modifications across recursive calls. Prefer passing state as parameters or returning results.

What is the iterative alternative to recursive tree traversal?

Iterative traversal uses an explicit stack (or queue) to simulate recursion. For example, inorder traversal can be done with a stack to emulate the recursive call stack. This avoids stack overflow and gives more control over memory use.