CODEWITHSUNDEEP
javascriptrecursionpathtree
user1261710
user1261710

Reputation: 2639

How to build the path to each node in a tree recursively - JavaScript?

My data structure will look like this:

var tree = [
    {
        id: 1,
        children: []
    }, {
        id: 2,
        children: [
            {
                id: 3,
                children: []
            }
        ]
    }
];

There can be any number of nodes or children on one branch.

My goal is to build a path to every node.

For example id: 3 will have a path of 1 > 2 > 3 id: 2 will have a path of 1 > 2

I want to run my tree through the algorithm so it will be modified like this:

 var tree = [
        {
            id: 1,
            path: [1],
            children: []
        }, {
            id: 2,
            path: [2],
            children: [
                {
                    id: 3,
                    path: [2, 3],
                    children: []
                }
            ]
        }
    ];

I have written an algorithm that will visit all of the nodes in the tree: https://plnkr.co/edit/CF1VNofzpafhd1MOMVfj

How can I build the path to each node?

Here is my attempt:

function traverse(branch, parent) {

  for (var i = 0; i < branch.length; i++) {

    branch[i].visited = true;

    if (branch[i].path === undefined) {
      branch[i].path = [];
    }

    if (parent != null) {
      branch[i].path.push(parent);
    }

    if (branch[i].children.length > 0) {
      traverse(branch[i].children, branch[i].id);
    }

  }

}

Upvotes: 3

Views: 3561

Answers (3)

Nenad Vracar
Nenad Vracar

Reputation: 122027

You could use reduce method to create a recursive function and pass the previous path values in recursive calls as an array of id's.

var tree = [{ id: 1, children: [] }, { id: 2, children: [{ id: 3, children: [] }] }];

function getPaths(data, prev = []) {
  return data.reduce((r, { id, children }) => {
    const o = { id, children, path: [...prev, id] }
    
    if (children) {
      o.children = getPaths(children, o.path)
    }
    
    r.push(o)
    return r
  }, [])
}

console.log(getPaths(tree))

Upvotes: 1

Mulan
Mulan

Reputation: 135187

You made a mistake

Your root node is an array, but all other nodes are objects.

This makes your program inconsistent and needlessly complex to handle the root node difference – the solution is to stop writing data using literals – you're bound to make mistakes like you did above

Instead, just make some simple data constructors and your complexities vanish into thin air

const Node = (id, ...children) =>
  ({ id, children })

const PathNode = (id, path, ...children) =>
  ({ id, path, children })

const addPaths = ({id, children}, acc = []) =>
  PathNode (id, acc, children.map (child =>
    addPaths (child, [...acc, id])))
    
const tree =
  Node (0, Node (1),
           Node (2, Node (3)))

console.log (tree)
// { id: 0, children: [
//   { id: 1, children: [ ] },
//   { id: 2, children: [
//     { id: 3, children: [ ] } ] } ] }

console.log (addPaths (tree))
// { id: 0, path: [ ], children: [
//   { id: 1, path: [ 0 ], children: [ ] },
//   { id: 2, path: [ 0 ], children: [
//     { id: 3, path: [ 0, 2 ], children: [ ] } ] } ] }

Upvotes: 1

Nina Scholz
Nina Scholz

Reputation: 386520

Beside the unclear taking of not directly involved parents, you could store the path as arrray and take it for each nested iteration.

function iter(path) {
    path = path || [];
    return function (o) {
        o.path = path.concat(o.id);
        if (o.children) {
            o.children.forEach(iter(o.path));
        }
    }
}

var tree = [{ id: 1, children: [] }, { id: 2, children: [{ id: 3, children: [] }] }];

tree.forEach(iter());
console.log(tree);
.as-console-wrapper { max-height: 100% !important; top: 0; }

Upvotes: 3

Related Questions