Recursive Tree insertion in Javascript

Question

I try to write insert into a tree data structure recursively in javascript with tree-node, but don't get it working. So my question would be, how to approach the issue.

this is my data:

[ { id: 'a', children: [ 'b', 'c' ] },
  { id: 'b', children: [ '' ] },
  { id: 'c', children: [ 'b', 'd' ] },
  { id: 'd', children: [ 'b' ] } ]

I want that showing up in a tree like the following:

 a
/\
b c
  /\
 b  d
     \
      b

Edit: Added code

I Thought i could do something like this, but that doesn't work... and of course has high complexity because of the nested forEach:

var Node = require("tree-node");
var testarray =     
[ 
{ id: 'a', children: [ 'b', 'c' ] },
{ id: 'b', children: [ '' ] },
{ id: 'c', children: [ 'b', 'd' ] },
{ id: 'd', children: [ 'b' ] } 
]

function appendChildRecursive(parent) {
    var childnode = new Node()
    var data = parent.data("children")
    testarray.forEach(function(item){
        if(data !== undefined) {
            data.forEach(function (child) {
                if (item.id == child) {
                    childnode.data("id", child).data("children", item.children)
                    childnode = appendChildRecursive(childnode)
                    parent.appendChild(childnode) 
                }
            })
        }

    })
    return parent
}

var root = new Node();
root.data("id",testarray[0].id).data("children",testarray[0].children)
root=appendChildRecursive(root)

do you really have node b twice? it generates a circular reference. — Nina Scholz
– Nina Scholz, Commented Jun 15, 2017 at 9:05
yes at least three times, but it doesn't create a circular as b is not pointing to one of it's callers. — Flo
– Flo, Commented Jun 15, 2017 at 9:10
how do you separate the nodes? or do you use a strict order beginning from the start and use only the last same named nodes? — Nina Scholz
– Nina Scholz, Commented Jun 15, 2017 at 9:12
That could be copys. It must not be the same node, just the values. — Flo
– Flo, Commented Jun 15, 2017 at 9:21

Nina Scholz · Accepted Answer · 2020-06-11 15:10:59Z

3

You could use a hash table for the last inserted nodes and keep the reference to the last nodes by overwriting the reference.

var data = [{ id: 'a', children: ['b', 'c'] }, { id: 'b', children: [] }, { id: 'c', children: ['b', 'd'] }, { id: 'd', children: ['b'] }],
    tree = function (array) {
        var nodes = Object.create(null),
            r = {};
        array.forEach(function (a) {
            if (!nodes[a.id]) {
                nodes[a.id] = { id: a.id, children: [] };
                r = nodes[a.id];
            }
            a.children.forEach(function (b) {
                nodes[b] = { id: b, children: [] };
                nodes[a.id].children.push(nodes[b]);
            });
        });
        return r;
    }(data);

console.log(tree);

.as-console-wrapper { max-height: 100% !important; top: 0; }

edited Jun 11, 2020 at 15:10

answered Jun 15, 2017 at 9:29

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Siraj Alam Over a year ago

You've passed the data in function as an array, but haven't used array anywhere and mutating data directly, why?

Lazyexpert · Accepted Answer · 2017-06-15 08:49:38Z

0

Your data structure is wrong. Each 'leaf' should contain reference to the 'left' and 'right' element. for example:

const first = { id: 'a', left: null, right: null };
const second = { id: 'b', left: null, right: first };
// etc...

The children approach would be more suitable for graph. But you still have to store references, not ids.

answered Jun 15, 2017 at 8:49

Lazyexpert

3,1741 gold badge22 silver badges33 bronze badges

2 Comments

Flo Over a year ago

but left/right is only for binary trees, no? In my case I could have more then two children, so I cannot make use of right and left.

Lazyexpert Over a year ago

Yes, you're right. It's my miss. Still I would store references, not ids.

Collectives™ on Stack Overflow

Recursive Tree insertion in Javascript

Edit: Added code

2 Answers 2

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Edit: Added code

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related