Filter for one specific node in JSON, show direct parents and all children

Question

Given the following JSON object;

const data = [
    { "id": 1, "name": "Node 1", "children": [
            { "id": 3, "name": "Node 1.1", "children": [
                    { "id": 6, "name": "Node 1.1.1", "children": [
                            { "id": 12, "name": "Node 1.1.1.1", "children": [] }
                        ]
                    },
                    { "id": 7, "name": "Node 1.1.2", "children": [
                            { "id": 13, "name": "Node 1.1.2.1", "children": [] }
                        ]
                    }
                ]
            },
            { "id": 4, "name": "Node 1.2", "children": [
                { "id": 8, "name": "Node 1.2.1", "children": [] },
                { "id": 9, "name": "Node 1.2.2", "children": [
                        { "id": 14, "name": "Node 1.2.2.1", "children": [] },
                        { "id": 15, "name": "Node 1.2.2.2", "children": [] }
                    ]
                }
            ]
        }
        ]
    },
    { "id": 2, "name": "Node 2", "children": [
            { "id": 5, "name": "Node 2.1", "children": [
                    { "id": 10, "name": "Node 2.1.1", "children": [] },
                    { "id": 11, "name": "Node 2.1.2", "children": [
                            { "id": 16, "name": "Node 2.1.2.1", "children": [] }
                        ]
                    }
                ]
            }
        ]
    }
];

I want to be able to find a specific node by ID and once that node is found get its direct parents and all children. For example, if I want to find the node with ID 9 (Node 1.2.2), I want it to return Node 1, Node 1.2, Node 1.2.2 and its children, and ignore everything else. I've got this partially working with this findById function;

findById(data, id)
{
    let node = '';
    data.some((currentNode) => {
        return node = id === currentNode.id ? currentNode : this.findById(currentNode.children, id);
    });
    return node;
}

which is called like this;

this.data = [this.findById(this.data, id)];

but it doesn't do exactly what I want. It finds the correct node (so in this case 1.2.2) and its children (1.2.2.1 and 1.2.2.2), but not its direct parents (1.2 and 1). How could I change the findById function to also include the direct parents?

The desired output would be;

const found = [
    { "id": 1, "name": "Node 1", "children": [
            { "id": 4, "name": "Node 1.2", "children": [
                    { "id": 9, "name": "Node 1.2.2", "children": [
                            { "id": 14, "name": "Node 1.2.2.1", "children": [] },
                            { "id": 15, "name": "Node 1.2.2.2", "children": [] }
                        ]
                    }
                ]
            }
        ]
    }
];

Answer 1

The first question is, is this the correct data structure? Can you implement this in a Linked List? If so, you can have specific references to grandparent nodes, parent nodes. If the data is relatively small, the search time is linear and insertion and deletion is linear.

class Node {
  constructor(value){
    this.value = value;
    this.next = null;
    this.children = [];
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0
    }

  insert(value) {
    let node = new Node(value);
    if(!this.head) {
      this.head = node;
    } else {
      this.tail.next = node;
    }
    this.tail = node;
    this.size++;
  }

  findNode(value) {
    let node = this.head;
    while(!!node) {
      if(node.value === value){
        return node;
      }
      node = node.next;
    }
    return `no node with ${value} found`
  }

  forEach(callback) {
    let node = this.head;
    while(!!node) {
      callback(node.value);
      node = node.next;
    }
  }

  print() {
    if(!this.head) {
      return null
    } else {
      let node = this.head;
      while(!!node){
        console.log(node.value);
        node = node.next
      }
    }

Answer 2

Recursion is a functional heritage and so here is a solution using functional style -

// identity : 'a -> 'a
const identity = x =>
  x

// findById : (number, node array) -> node?
const findById = (q = 0, [ n, ...more ], exit = identity) =>
  n === undefined
    ? false
    : findById1 (q, n, exit)
      || findById (q, more, exit)

// findById1 : (number, node) -> node?
const findById1 = (q = 0, n = {}, exit = identity) =>
  n.id === q
    ? exit (n)
    : findById (q, n.children, r =>
        exit ({...n, children: [ r ] })
      )

It works like this -

findById (9, data)
// { id: 1, name: "Node 1", children: [
//   { id: 4, name: "Node 1.2", children: [
//     { id: 9, name: "Node 1.2.2", children: [
//         { id: 14, name: "Node 1.2.2.1", children: [] },
//         { id: 15, name: "Node 1.2.2.2", children: [] }
//     ]}
//   ]}
// ]}

When an id cannot be found, false is returned -

findById (99, data)
// false

Expand the snippet below to verify the results in your own browser -

const identity = x =>
  x

const findById = (q = 0, [ n, ...more ], exit = identity) =>
  n === undefined
    ? false
    : findById1 (q, n, exit)
      || findById (q, more, exit)

const findById1 = (q = 0, n = {}, exit = identity) =>
  n.id === q
    ? exit (n)
    : findById (q, n.children, r =>
        exit ({...n, children: [ r ] })
      )

const data =
  [{id:1, name:"Node 1", children:[{id:3, name:"Node 1.1", children:[{id:6, name:"Node 1.1.1", children:[{id:12, name:"Node 1.1.1.1", children:[]}]},{id:7, name:"Node 1.1.2", children:[{id:13, name:"Node 1.1.2.1", children:[]}]}]},{id:4, name:"Node 1.2", children:[{id:8, name:"Node 1.2.1", children:[]},{id:9, name:"Node 1.2.2", children:[{id:14, name:"Node 1.2.2.1", children:[]},{id:15, name:"Node 1.2.2.2", children:[]}]}]}]},{id:2, name:"Node 2", children:[{id:5, name:"Node 2.1", children:[{id:10, name:"Node 2.1.1", children:[]},{id:11, name:"Node 2.1.2", children:[{id:16, name:"Node 2.1.2.1", children:[]}]}]}]}]

console.log (findById (9, data))
// { id: 1, name: "Node 1", children: [
//   { id: 4, name: "Node 1.2", children: [
//     { id: 9, name: "Node 1.2.2", children: [
//         { id: 14, name: "Node 1.2.2.1", children: [] },
//         { id: 15, name: "Node 1.2.2.2", children: [] }
//     ]}
//   ]}
// ]}

console.log (findById (99, data))
// false

---

Continuation-passing style leaks the exit param in the function's interface. Using a helper function, we can create an api that matches your original -

// export findById : (number, node array) -> node? 
const findById = (q = 0, nodes = []) =>
  findAny (q, nodes, identity)

// private
const findAny = (q, [ node, ...more ], exit) =>
  node === undefined
    ? false
    : find1 (q, node, exit)
      || findAny (q, more, exit)

// private
const find1 = (q, node, exit) =>
  node.id === q
    ? exit (node)
    : findAny (q, node.children, r =>
        exit ({...node, children: [ r ] })
      )

---

Lastly, we could modify our original implementation to create a higher-order findBy, which instead of taking an id input, it accepts a function similar to Array.prototype.find -

// export findBy : ('node -> bool, node array) -> node?
const findBy = (f = identity, nodes = []) =>
  findAny (f, nodes, identity)

// private
const findAny = (f, [ node, ...more ], exit) =>
  node === undefined
    ? false
    : find1 (f, node, exit)
      || findAny (f, more, exit)

// private
const find1 = (f, node, exit) =>
  f (node)
    ? exit (node)
    : findAny (f, node.children, r =>
        exit ({...node, children: [ r ] })
      )

More specific functions like findById and findByName can easily be implemented by specialising findBy -

// export findById : (number, node array) -> node? 
const findById = (q = 0, nodes = []) =>
  findBy (n => n.id === q, nodes, identity)

// export findByName : (string, node array) -> node? 
const findByName = (q = "", nodes = []) =>
  findBy (n => n.name === q, nodes, identity)

Or you can find by any arbitrary thing -

findBy (node => node.id > 100 && node.name.length < 20, data)
// ...

Hopefully this begins to illustrate some of the advantages of functional style.

Answer 3

You just need to store the result of your recursive function. To do this separate your ternary into an if else like below:

function findById(data, id) {
    let node = null;

    data.some((currentNode) => {
        if (id === currentNode.id) {
            return node = [currentNode];
        }

        const inItsTree = findById(currentNode.children, id);
        if (inItsTree) {
            return node = [{ ...currentNode, children: inItsTree }];
        }
    });

    return node;
}

const data = [{"id":1,"name":"Node 1","children":[{"id":3,"name":"Node 1.1","children":[{"id":6,"name":"Node 1.1.1","children":[{"id":12,"name":"Node 1.1.1.1","children":[]}]},{"id":7,"name":"Node 1.1.2","children":[{"id":13,"name":"Node 1.1.2.1","children":[]}]}]},{"id":4,"name":"Node 1.2","children":[{"id":8,"name":"Node 1.2.1","children":[]},{"id":9,"name":"Node 1.2.2","children":[{"id":14,"name":"Node 1.2.2.1","children":[]},{"id":15,"name":"Node 1.2.2.2","children":[]}]}]}]},{"id":2,"name":"Node 2","children":[{"id":5,"name":"Node 2.1","children":[{"id":10,"name":"Node 2.1.1","children":[]},{"id":11,"name":"Node 2.1.2","children":[{"id":16,"name":"Node 2.1.2.1","children":[]}]}]}]}];

console.log(findById(data, 9));

Answer 4

Modified your findById method as:

function findById(data, id, parent)
{
    let node = '';
    data.some((currentNode) => {
      if(id === currentNode.id) {
        node = currentNode;
      } else {
        parent.push(currentNode); // track parent node
        node = this.findById(currentNode.children, id, parent);
      }
      return node;
    });
    return {node: node, parent: parent};
}

this.data = [this.findById(this.data, 6, [])];

console.log(this.data[0].node); // will give you current node with children
console.log(this.data[0].parent); // will give you array of parents node