Get All Paths of a Binary Tree

Given a binary tree, return all root-to-leaf paths of the tree.

This problem can be solved by applying depth-first traversal and processing each level in the pre-order manner. A path is represented as a stack of nodes. A new node is pushed to the current path stack at every node. If the current node is a leaf node, then a new instance of the current path stack is added to the collection of paths. If the current node is not a leaf node, proceed to the next level of the tree.

One important note to keep in mind is that arrays (conceptually stack) are passed as reference. This means that extra care must be taken to ensure that the current path stack only contains the path up to that level and nothing more. There are a few approaches to doing this.

One way is to keep track of the height of the current level being processed and use that height as an index to modify the value of the array. Once a leaf node is reached, add the subarray from 0 to the height to the collections of path. This approach may not work if the stack implementation does not permit access via index. The second technique is to instantiate a new stack at every level to avoid the unintended pass-by-reference problem. This approach may be memory intensive if the binary tree is large. The last approach is to pop the most recent node once the left and right children are processed.

const collectPaths = (root) => {
  const paths = [];
  collectPaths(root, [], paths);
  return paths;
}

const collectPaths = (root, currentPath, paths) {
  if (!root)
    return;

  path.push(root.value);

  if (!root.left && !root.right)
    paths.push([...path]);

  collectPaths(root.left, path, paths);
  collectPaths(root.right, path, paths);
  path.pop();
}

The time complexity of this problem is O(n) because all nodes are processed.