Javascript: Find all parents for element in tree

Question

I have the objects tree, and i can't found all parents for concrete object id. Imagine i need to add some new field to each parent for object with id = 5. Can someone help please with recursive loop through tree

var tree = {
  id: 1,
  children: [
  	{
		id: 3,
		parentId: 1,
		children: [
		  	{
				id: 5,
				parentId: 3,
				children: []
			}
		]
	}
  ]
}

console.log(searchTree (tree, 5));

function searchTree (tree, nodeId){
      for (let i = 0; i < tree.length; i++){
        if (tree[i].id == nodeId) {
            // it's parent
            console.log(tree[i].id);
            tree[i].newField = true;
            if (tree[i].parentId != null) {
              searchTree(tree, tree[i].parentId);
            }
        }
      }
 }

Answer 1

data constructors

People need to stop writing data like this:

const tree = 
  { id: 1, parentId: null, children:
    [ { id: 3, parentId: 1, children:
      [ { id: 5, parentId: 3, children: [] } ] } ] }

and start writing data using data constructors

// "Node" data constructor
const Node = (id, parentId = null, children = Children ()) =>
  ({ id, parentId, children })

// "Children" data constructor
const Children = (...values) =>
  values

// write compound data
const tree =
  Node (1, null, 
    Children (Node (3, 1,
      Children (Node (5, 3)))))

console.log (tree)
// { id: 1, parentId: null, children: [ { id: 3, parentId: 1, children: [ { id: 5, parentId: 3, children: [] } ] } ] }

This allows you to separate your mind from details like whether {}, or [] or even x => ... is used to contain your data. I would go just one step further and create a uniform interface with a guaranteed tag field – so that it could later be distinguished from other generic datum

It's perfect that stack-snippets butchers the output in this program below. It does not matter what the data looks like when printed out – what matters is it's easy for us humans to read/write in our program, and it's easy for our program to read/write

When/if you need it in a specific format/shape, coerce it into that shape then; until that point, keep it nice an easy to work with

const Node = (id, parentId = null, children = Children ()) =>
  ({ tag: Node, id, parentId, children })

const Children = (...values) =>
  ({ tag: Children, values })

// write compound data
const tree =
  Node (1, null, 
    Children (Node (3, 1,
      Children (Node (5, 3)))))

console.log (tree)
// { ... really ugly output, but who cares !.. }

---

let's get searching

We can write search with a simple loop helper function – but notice what you're not seeing; almost no logic (a single ternary expression is used); no imperative constructs like for/while or manual iterator incrementing like i++; no use of mutators like push/unshift or effectful functions like .forEach; no senseless inspection of .length property or direct index reads using [i]-style lookups – it's just functions and calls; we don't have to worry about any of that other noise

const Node = (id, parentId = null, children = Children ()) =>
  ({ tag: Node, id, parentId, children })

const Children = (...values) =>
  ({ tag: Children, values })

const tree =
  Node (1, null, 
    Children (Node (3, 1,
      Children (Node (5, 3)))))

const search = (id, tree = null) =>
  {
    const loop = (path, node) =>
      node.id === id
        ? [path]
        : node.children.values.reduce ((acc, child) =>
            acc.concat (loop ([...path, node], child)), [])
    return loop ([], tree)
  }

const paths =
  search (5, tree) 

console.log (paths.map (path => path.map (node => node.id)))
// [ 1, 3 ]

So search returns an array of paths, where each path is an array of nodes – why is this the case? In the event a child with an ID of X appears in multiple locations in the tree, all paths to the child will be returned

const Node = (id, parentId = null, children = Children ()) =>
  ({ tag: Node, id, parentId, children })

const Children = (...values) =>
  ({ tag: Children, values })

const tree =
  Node (0, null, Children (
    Node (1, 0, Children (Node (4, 1))),
    Node (2, 0, Children (Node (4, 2))),
    Node (3, 0, Children (Node (4, 3)))))

const search = (id, tree = null) =>
  {
    const loop = (path, node) =>
      node.id === id
        ? [path]
        : node.children.values.reduce ((acc, child) =>
            acc.concat (loop ([...path, node], child)), [])
    return loop ([], tree)
  }
  
const paths =
  search (4, tree) 

console.log (paths.map (path => path.map (node => node.id)))
// [ [ 0, 1 ],
//   [ 0, 2 ],
//   [ 0, 3 ] ]

---

you accidentally wrote the list monad

The list monad encodes the idea of ambiguous computations – that is, the idea of a computation that can return one or more result. Let's make a small change to our program - this is advantageous because List is generic and now can be used other places in our program where this kind of computation is essential

If you like this solution, you will probably enjoy reading my other answers that talk about the list monad

const List = (xs = []) =>
  ({
    tag:
      List,
    value:
      xs,
    chain: f =>
      List (xs.reduce ((acc, x) =>
        acc.concat (f (x) .value), []))
  })

const Node = (id, parentId = null, children = Children ()) =>
  ({ tag: Node, id, parentId, children })

const Children = (...values) =>
  List (values)

const search = (id, tree = null) =>
  {
    const loop = (path, node) =>
      node.id === id
        ? List ([path])
        : node.children.chain (child =>
            loop ([...path, node], child))
    return loop ([], tree) .value
  }
  
const tree =
  Node (0, null, Children (
    Node (1, 0, Children (Node (4, 1))),
    Node (2, 0, Children (Node (4, 2))),
    Node (3, 0, Children (Node (4, 3)))))

const paths =
  search (4, tree) 

console.log (paths.map (path => path.map (node => node.id)))
// [ [ 0, 1 ],
//   [ 0, 2 ],
//   [ 0, 3 ] ]

Answer 2

A recursion function isn't that difficult. Remember that you pass the new level onto the function if your parameter isn't met.

var tree = [{
  id: 1,
  children: [{
    id: 3,
    parentId: 1,
    children: [{
      id: 5,
      parentId: 3,
      children: [{
        id: 6,
        parentId: 5,
        children: [{
          id: 5,
          parentId: 3,
          children: []
        }]
      }]
    }]
  }]
}]; //wrap first obj in an array too.

searchTree(tree, 5);
console.log(tree);

function searchTree(tree, nodeId) {
  for (let i = 0; i < tree.length; i++) {
    if (tree[i].id == nodeId) {
      tree[i]; //id found, now add what you need.
      tree[i].newField = "added";
    }//if child has children of its own, continu digging.
    if (tree[i].children != null && tree[i].children.length > 0) {
      searchTree(tree[i].children, nodeId); //pass the original nodeId and if children are present pass the children array to the function.

    }
  }
}

Answer 3

The easiest solution is to flatten the tree structure down so you can just look up ids and do a simple while loop

var tree = {
  id: 1,
  children: [
  	{
		id: 3,
		parentId: 1,
		children: [
		  	{
				id: 5,
				parentId: 3,
				children: []
			}
		]
	}
  ]
}

// We will flatten it down to an object that just holds the id with the object
var lookup = {}
function mapIt (node) {
  lookup[node.id] = node;
  //recursive on all the children
  node.children && node.children.forEach(mapIt);
}
mapIt(tree)

// This takes a node and loops over the lookup hash to get all of the ancestors
function findAncestors (nodeId) {
   var ancestors = []
   var parentId = lookup[nodeId] && lookup[nodeId].parentId
   while(parentId !== undefined) {
     ancestors.unshift(parentId)
     parentId = lookup[parentId] && lookup[parentId].parentId
   }
   return ancestors;
}

// Let us see if it works
console.log("5: ",  findAncestors(5))

Answer 4

Here is an example of a working recursive function.

Play around with it for a while and you should be golden

var tree = {
  id: 1,
  children: [{
    id: 3,
    parentId: 1,
    children: [{
      id: 5,
      parentId: 3,
      children: []
    }]
  }]
}

function mapit(node, parent = null) {
  node.parent = parent;
  if (node.children.length > 0) {
    for (var i = 0; i < node.children.length; i++) {
      var child = node.children[i];
      mapit(child, node);
    }
  }
}
mapit(tree);
console.log(tree);