Tree recursion in JavaScript and how to optimize

What Is Tree Recursion?

Tree recursion is a technique used to traverse a tree-like data structure by recursively visiting each node and its children. It’s widely used in computer science, particularly in algorithms that operate on trees and graphs.

In JavaScript, tree recursion is typically implemented using a recursive function that takes a node as input and calls itself on each of its child nodes until all nodes have been visited.

A Simple Example

Let’s define a basic binary tree using a TreeNode class:

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);

Now, we’ll write a recursive function to traverse the tree in pre-order (root → left → right):

function traverse(node) {
  if (node === null) return;
  console.log(node.val);
  traverse(node.left);
  traverse(node.right);
}

traverse(root); // Outputs: 1 2 3

This function checks if the node is null (the base case). If not, it prints the node’s value and continues recursively down the left and right branches.

The Problem: Deep Trees and Stack Overflow

While this approach is elegant and readable, it can lead to stack overflow errors for trees that are very deep. Every recursive call consumes a stack frame, and JavaScript doesn’t handle deep recursion well in most engines.

Can We Optimize It with Tail Recursion?

One proposed optimization is tail recursion, which restructures the recursive function so that the recursive call is the last thing it does. In some languages, this allows the compiler or interpreter to reuse the current stack frame, avoiding growth of the call stack.

Here’s a tail-recursive-style version of the traversal:

function traverseTail(node) {
  function traverseHelper(node, acc) {
    if (node === null) {
      return acc;
    }
    acc.push(node.val);
    return traverseHelper(node.right, traverseHelper(node.left, acc));
  }
  return traverseHelper(node, []);
}

console.log(traverseTail(root)); // Outputs: [1, 2, 3]

This version accumulates the result in an array (acc) passed down through each call. It still recursively visits the left and right nodes but does so in a way that accumulates values instead of printing them.

⚠️ Important Note: No Tail Call Optimization in JavaScript

Despite being written in a tail-recursive style, this function does not benefit from tail call optimization in current JavaScript engines. Although the ECMAScript 2015 (ES6) spec allows it, most modern JavaScript engines (like V8) do not implement tail call optimization.

So while this version is more functional and allows result collection, it still uses the call stack and does not eliminate the risk of stack overflow.

For Truly Deep Trees, Go Iterative

If stack safety is critical—such as when dealing with large or unbalanced trees—the most reliable solution is to switch to an iterative approach using an explicit stack:

function traverseIterative(root) {
  const stack = [root];
  const result = [];

  while (stack.length > 0) {
    const node = stack.pop();
    if (node) {
      result.push(node.val);
      stack.push(node.right);
      stack.push(node.left);
    }
  }

  return result;
}

console.log(traverseIterative(root)); // Outputs: [1, 2, 3]

This avoids recursion entirely, making it safe even for deeply nested trees.

Recap

Tree recursion is elegant but can cause stack overflows.
Tail-recursive styles can make code more functional and testable.
However, JavaScript engines don’t optimize tail calls, so the call stack is still used.
For deep trees, the safest and most efficient method is an iterative solution using an explicit stack.

Tags: technology, programming, javascript, data structures, algorithms