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 ] ]