get paths from nary tree with node example in javascript

Here's an example of a recursive function in JavaScript that can traverse an n-ary tree and return all possible paths from the root node to leaf nodes:

index.tsx
class TreeNode {
  constructor(val, children) {
    this.val = val;
    this.children = children || [];
  }
}

function findPaths(root) {
  const result = [];

  function traverse(node, path) {
    path.push(node.val);

    if (node.children.length === 0) {
      result.push(path.slice()); // make a copy of the current path and add it to result
    } else {
      for (let child of node.children) {
        traverse(child, path);
      }
    }

    path.pop();
  }

  if (root) {
    traverse(root, []);
  }

  return result;
}

// Example usage:
const tree = new TreeNode(1, [
  new TreeNode(2, [
    new TreeNode(4),
    new TreeNode(5),
  ]),
  new TreeNode(3, [
    new TreeNode(6),
  ]),
]);

console.log(findPaths(tree));
// Output: [[1, 2, 4], [1, 2, 5], [1, 3, 6]]
775 chars
45 lines

In the example above, we define a TreeNode class to represent nodes in the n-ary tree. The findPaths function takes a root node as input, initializes an empty result array, and calls a recursive traverse function on the root node. The traverse function takes two inputs: a node and an array representing the current path from the root to the node. We push the value of the current node onto the path array and check if it is a leaf node (i.e., has no children). If it is a leaf node, we copy the current path and add it to the result array. If it is not a leaf node, we recursively call traverse on each child node, passing in the current path array. After traversing all children, we remove the current node from the path array using the pop method. Finally, we return the result array containing all paths from the root node to leaf nodes.

gistlibby LogSnag