What Is Tree Recursion? 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. tree-like data structure 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 of Tree Recursion Let’s define a basic binary tree using a TreeNode class: TreeNode 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); 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): traverse 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 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. null The Problem with Tree Recursion: 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. stack overflow errors 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. tail recursion last thing it does reuse the current stack frame 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] 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. acc accumulates values 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. Note: No Tail Call Optimization in JavaScript 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. tail-recursive style does not benefit from tail call optimization 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. still uses the call stack 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: large or unbalanced trees iterative approach 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] 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. 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. JavaScript engines don’t optimize tail calls For deep trees, the safest and most efficient method is an iterative solution using an explicit stack. iterative solution © 2025 John Moscarillo. All Rights Reserved
