get paths from nary tree in javascript

To get paths from a n-ary tree, we can use depth-first search algorithm. We can start from the root node and traverse all the child nodes recursively, while keeping track of the current path. When we reach a leaf node, we add the current path to the result.

Here's the example code:

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

function getPaths(root) {
  const result = [];
  dfs(root, [], result);
  return result;
}

function dfs(node, path, result) {
  if (!node) {
    return;
  }
  path.push(node.val);
  if (node.children.length === 0) {
    result.push([...path]);
  } else {
    for (let i = 0; i < node.children.length; i++) {
      dfs(node.children[i], path, result);
    }
  }
  path.pop();
}
489 chars
28 lines

In this code, we define a TreeNode class to represent n-ary tree nodes, which contains a value and an array of child nodes.

The getPaths function takes the root node as an argument and returns an array of paths. The dfs function is a helper function that takes the current node, the current path, and the result array.

Inside dfs, we add the current node value to the path and check if the node is a leaf node. If it is, we add the current path to the result. If not, we iterate over each child node and call the dfs function recursively.

Finally, we remove the last element from the path array using pop method.

Here's an example usage:

index.tsx
const root = new TreeNode(1, [new TreeNode(2), new TreeNode(3, [new TreeNode(4), new TreeNode(5)]), new TreeNode(6)]);

console.log(getPaths(root)); // [[1, 2], [1, 3, 4], [1, 3, 5], [1, 6]]
191 chars
4 lines

This will output an array of four paths as expected.

gistlibby LogSnag