CODEWITHSUNDEEP
javascriptsearchtreetreeview
JasonHsieh
JasonHsieh

Reputation: 591

javascript array tree search keep the node and parents

Trying to implement a tree search function which takes an array(tree structure) and a string keyword, would return an tree array but only keep the matched nodes and its parents.

function search(nodes, keyword){

}



const nodes = [
  {
    value: "1-1",
    children: [
      { value: "1-1-1"},
      { value: "1-1-2", children:[
        {
          value: "1-1-2-1",
          children: [
            { value: "1-1-2-1-1" },
            { value: "1-1-2-1-2" }
          ]
        },
        {
          value: "1-1-2-2"
        }
      ] }
    ]
  },
  {
    value: "1-2",
    children: [
      { value: "1-2-1"},
      { value: "1-2-2", children:[
        {
          value: "1-2-2-1",
          children: [
            { value: "1-2-2-1-1" },
            { value: "1-2-2-1-2" }
          ]
        },
        {
          value: "1-2-2-2"
        }
      ] }
    ]
  },
];

expected output would be an tree with nodes' values contain "1-1-2-1" and its parents as below

const searchedNodes = search(nodes, "1-1-2-1"); 



[
    {
    value: "1-1",
    children: [
      { value: "1-1-2", children:[
        {
          value: "1-1-2-1",
          children: [
            { value: "1-1-2-1-1" }
          ]
        }
      ] }
    ]
  }
]
*/

2018-06-26 Updated

I made a working one(DFS) but probably not pretty efficient.

const search = (nodes, keyword) => {
    let newNodes = [];
    for (let n of nodes) {
      if (n.children) {
        const nextNodes = this.keywordFilter(n.children, keyword);
        if (nextNodes.length > 0) {
          n.children = nextNodes;
        } else if (n.label.toLowerCase().includes(keyword.toLowerCase())) {
          n.children = nextNodes.length > 0 ? nextNodes : [];
        }
        if (
          nextNodes.length > 0 ||
          n.label.toLowerCase().includes(keyword.toLowerCase())
        ) {

          newNodes.push(n);
        }
      } else {
        if (n.label.toLowerCase().includes(keyword.toLowerCase())) {
          newNodes.push(n);
        }
      }
    }
    return newNodes;
  };

Upvotes: 1

Views: 2503

Answers (1)

Nina Scholz
Nina Scholz

Reputation: 386600

You need to iterate the nodes of the same level and check if the value is equal, then take that node and exit the loop. Otherwise check the children and generate a new object for preventing to mutate the original data.

function search(nodes, value) {
    var result;

    nodes.some(o => {
        var children;
        if (o.value === value) {
            return result = o;
        }
        if (o.children && (children = search(o.children, value))) {
            return result = Object.assign({}, o, { children });
        }
    });

    return result && [result];
}


const nodes = [{ value: "1-1", children: [{ value: "1-1-1" }, { value: "1-1-2", children: [{ value: "1-1-2-1", children: [{ value: "1-1-2-1-1" }, { value: "1-1-2-1-2" }] }, { value: "1-1-2-2" }] }] }, { value: "1-2", children: [{ value: "1-2-1" }, { value: "1-2-2", children: [{ value: "1-2-2-1", children: [{ value: "1-2-2-1-1" }, { value: "1-2-2-1-2" }] }, { value: "1-2-2-2" }] }] }];

console.log(search(nodes, "1-1-2-1"));
.as-console-wrapper { max-height: 100% !important; top: 0; }

Upvotes: 3

Related Questions