Tree recursion in JavaScript and how to optimize

Tree recursion is a technique used to traverse a tree-like data structure by recursively visiting each node and its children. This type of recursion is commonly used in computer science, particularly in algorithms related to graphs and trees.

In JavaScript, tree recursion can be implemented using a recursive function that takes a node as input and recursively calls itself on each of its child nodes until all nodes have been visited. For example, let's consider a simple binary tree with a value and two child nodes:

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);

To traverse this tree recursively, we can write a function that takes a node as input and recursively calls itself on the node's left and right child nodes:

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 first checks if the input node is null, which indicates the end of the tree. If the node is not null, it prints its value and recursively calls itself on the node's left and right child nodes.

While tree recursion is a powerful technique, it can be inefficient and may lead to stack overflow errors if the tree is very deep. To optimize tree recursion in JavaScript, we can use a technique called tail recursion.

Tail recursion involves restructuring the recursive function so that the recursive call is the last operation performed. This allows the JavaScript engine to optimize the recursion, avoiding stack overflow errors and making the function more efficient.

Here's an example of a tail-recursive implementation of the tree traversal function:

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]

In this implementation, we use a helper function that takes an additional accumulator parameter. Instead of recursively calling itself directly on the child nodes, it calls itself on the right child node first, passing the accumulator as a parameter, then calls itself on the left child node, passing the updated accumulator.

This technique allows the recursive call to be the last operation performed, making the function tail-recursive and therefore more efficient. It also eliminates the need for the call stack, reducing the risk of stack overflow errors.