Build tree from edge pairs and root

I’m trying to write a program that takes an array of edge pairs and turns it into a tree. I’m given a root. In this example, the root is 2.

The only constraint is, each node can max have 2 children.

Sample input:

[[1,2],[2,3],[3,4],[1,5]]

Expected output:

{
   "id":2,
   "children":[
      {
         "id":1,
         "children":[
            {
               "id":5
            }
         ]
      },
      {
         "id":3,
         "children":[
            {
               "id":4
            }
         ]
      }
   ]
}
enter code here

Would look something like this:

       2
      / 
     1   3
    /         
   5       4

This is my attempt so far:

  const tree = {};
  const edgePairs = [[1, 2], [2, 3], [3, 4], [1, 5]];
  let root = 2;
  let children;

  function hasTwoChildren(node) {
    let counter = 0;
    for (const i in edgePairs) {
      if (edgePairs[i].includes(node)) counter++;
    }
    return counter === 2;
  }

  function getChildren(root) {
    const children = [];
    for (let i = 0; i < edgePairs.length; i++) {
      if (edgePairs[i][0] === root) children.push(edgePairs[i][1]);
      if (edgePairs[i][1] === root) children.push(edgePairs[i][0]);
    }
    return children;
  }

  function makeTree(tree, root) {
    if (tree.id === undefined) {
      tree.id = root;
    } else if (hasTwoChildren(root)) {
      children = getChildren(root);
      tree.children = makeTree(tree, children[0]);
      makeTree(tree, children[1]);
    } else {
      makeTree(tree, children[0]);
    }
    return tree;
  }

  for (const i in edgePairs) {
    makeTree(tree, root);
  }

Feel like this should be pretty simple but I’m missing something.. Any help? 🙂

Answer

Wow, I love this question. And is pretty challenging too! This was one of my first time to take a recursive approach to a certain problem. And I think I managed to figure this out.

let root = 2;

// more complicated data (with 1 branch that doesn't connect to any other node)
let nodes = [[1, 2], [2, 3], [3, 4], [1, 5], [1, 6], [2, 8], [100, 101]];


function createTree(root, nodes){
    
    let children = [];
    for (let i = 0; i < nodes.length; i++){
        const index_of_root = nodes[i].indexOf(root)
        if (index_of_root !== -1){
            children.push(nodes[i][Number(!index_of_root)]); // note that data like [1,2,4] or [1] will not work.
            nodes.splice(i, 1);
            i--; // after removing the element, decrement the iterator
        }
    }

    let tree = { 
        id:  String(root)
    };

    if (children.length !== 0){ // if there are any children, 
        tree.children = [];     // add the children property to the tree object
        for (let child of children){ 
            tree.children.push(createTree(child, nodes)); // then add the tree of each of the children
        }
    }
    return tree;
}    

console.log(createTree(root, nodes));

Basically, when the createTree() function notices that there are any node associated with the root, it creates a tree object with children property. That children property is filled with all the trees returned from each of the children associated with the root.

If there are no children, it simply returns a tree object without any children. Honestly my code might be a little hard to read for the reason of being a recursive one, so it might help to print some values in the middle of the function.

Now this one is with the constraint (just that if (index_of_root !== -1){ is replaced by if (index_of_root !== -1 && children.length !== 2){):

let root = 2;

// more complicated data (with 1 branch that doesn't connect to any other node)
let nodes = [[1, 2], [2, 3], [3, 4], [1, 5], [1, 6], [2, 8], [100, 101]];


function createTree(root, nodes){
    
    let children = [];
    for (let i = 0; i < nodes.length; i++){
        const index_of_root = nodes[i].indexOf(root)
        if (index_of_root !== -1 && children.length !== 2){
            children.push(nodes[i][Number(!index_of_root)]); // note that data like [1,2,4] or [1] will not work.
            nodes.splice(i, 1);
            i--; // after removing the element, decrement the iterator
        }
    }

    let tree = { 
        id:  String(root)
    };

    if (children.length !== 0){ // if there are any children, 
        tree.children = [];     // add the children property to the tree object
        for (let child of children){ 
            tree.children.push(createTree(child, nodes)); // then add the tree of each of the children
        }
    }
    return tree;
}    

console.log(createTree(root, nodes)); //notice how [2, 8] pair is excluded from the tree

Hope that helped. Cheers 🙂