title: Javascript tree search algorithm which return subset of the tree which contains the found term and its parents
body: <p>I have a tree selection in which every node has a name. I want to search through the node names and return a subset of the tree which only contains the found nodes and its parents.</p>
  
  <p>Does anybody know an efficient algorithm in JavaScript for this problem which return the node with all of its parents.</p>
  
  <p>Here is an example. when user type a search term, example "Elephant" and the tree looks like this:</p>
  
  <ul>
  <li>Elephant
  
  <ul>
  <li>Hamster 
  
  <ul>
  <li>Fish</li>
  </ul></li>
  <li>Duck</li>
  </ul></li>
  <li>Hamster
  
  <ul>
  <li>dog 
  
  <ul>
  <li>Fish</li>
  </ul></li>
  <li>Elephant
  
  <ul>
  <li>Fish</li>
  </ul></li>
  </ul></li>
  <li>Dog 
  
  <ul>
  <li>Fish 
  
  <ul>
  <li>Unicorn
  
  <ul>
  <li>Elephant </li>
  </ul></li>
  <li>Elephant      </li>
  <li>Hamster     </li>
  </ul></li>
  <li>Unicorn</li>
  </ul></li>
  <li>Elephant
  
  <ul>
  <li>Hamster 
  
  <ul>
  <li>Fish</li>
  <li>Elephant</li>
  <li>Elephant</li>
  </ul></li>
  <li>Elephant</li>
  </ul></li>
  </ul>
  
  <hr>
  
  <p>Would like to output the search result in tree format with children like this:</p>
  
  <ul>
  <li>Elephant</li>
  <li>Hamster
  
  <ul>
  <li>Elephant</li>
  </ul></li>
  <li>Dog 
  
  <ul>
  <li>Fish 
  
  <ul>
  <li>Unicorn
  
  <ul>
  <li>Elephant</li>
  </ul></li>
  <li>Elephant</li>
  </ul></li>
  </ul></li>
  <li>Elephant
  
  <ul>
  <li>Hamster 
  
  <ul>
  <li>Elephant</li>
  <li>Elephant</li>
  </ul></li>
  <li>Elephant</li>
  </ul></li>
  </ul>
  
  <p>Given: </p>
  
  <pre><code>this.tree =[
   {childs: Array(2), id: 2, name: "Elephant",  …}
   {childs: Array(2), id: 3, name: "Hamster", ...}
   {childs: Array(2), id: 3, name: "Dog", ...}
   {childs: Array(2), id: 3, name: "Elephant", ...}
  ]
  </code></pre>
  
  <p>Given</p>
  
  <pre><code>//  animal target name
  target = 'Elephant',
  
  //  tree data structure
  tree = [
      { name: 'Elephant', childs: [
          { name: 'Duck' },
          { name: 'Hamster', childs: [
              { name: 'Fish' }
          ]}
      ]},
      { name: 'Hamster', childs: [
          { name: 'Elephant', childs: [
              { name: 'Fish' }
          ]},
          { name: 'Dog', childs: [
              { name: 'Fish' }
          ]}
      ]},
      { name: 'Dog', childs: [
          { name: 'Unicorn' },
          { name: 'Fish', childs: [
              { name: 'Hamster' },
              { name: 'Unicorn', childs: [
                  { name: 'Elephant' }
              ]},
          ]}
      ]},
      { name: 'Elephant', childs: [
          { name: 'Duck' },
          { name: 'Hamster', childs: [
              { name: 'Elephant' },
              { name: 'Fish' },
          ]}
      ]}
  ],
  </code></pre>
  
  <p>Attempt to modify the tree from Nave's solution (output result in original tree object format, set property to display = false to hide the node, keep on searching the other node in the same level even if found matching node). 
  This seems like a DFS, however am still taking lots of time to figure the backtracking. Final result is to return the tree which contains only the matching result and its parent/ancestor.</p>
  
  <pre><code>searchHelper(term, children, showParent) {
      let found;
      if (showParent == null || showParent == undefined) {
          showParent = false;
      }
      children.forEach(child =&gt; {
          if (found = this.search(term, child)){
              console.log('found--------------------------------');
              child.display = true;
          } else {
              console.log('not foond-----------------------------------------')
              child.display = false;
          }
          showParent = showParent || found;
      })
      return showParent;
  }
  
  search(term, parent) {
      let ans, showParent, found, { name, children } = parent;
  
      if (children.length) {
          showParent = this.searchHelper(term, children, showParent);
      }
      return name.toLowerCase().indexOf(term.toLowerCase()) != -1;
  }
  
  this.search("Elephant", this.tree);
  </code></pre>