TreeNode Search Javascript

Question

I have a class called TreeNode

class TreeNode {
  constructor(name) {
    // Name of the node visible to user. It is string
    self.name = name;

    //  Children of the node. it is array of TreeNode
    self.children = [];

    // If this field is true, children of the Node are shown to the user
    self.expanded = false;

    // If this field is true, it means that the node matches the current search and it is emphasized
    self.matched = false;
  }

The task is to perform the following: /* This function returns a new subtree of the original tree which satisfies the following requirements:

• Function doesn't modify the original tree

• The 'Node matches the searched' term means that Node's name contains the 'search' as a substring (case insensitive)

• Node is included in the resulting subtree if Node, one of its ancestors, or one of its descendants matches the search

• If Node matches the search, its matched property must be set to true, otherwise false

• If at least one descendant of the Node matches the search, Node's expanded property must be set to true, otherwise false

  @returns TreeNode | null */

  makeTreeForSearchQuery(search) { // Do Something here return null; } }

I have a function within the class

makeTreeForSearchQuery(search)
{
if (self.children != null)
    {
        for(var i=0; i < self.children.length; i++)
        {
            self.children[i]= makeTreeForSearchQuery(search);
            if(children.matched[i] == true)
            {
                //self.parent = children.matched[i];
                //self.expanded = true;
            }
            
            //Something needs to be done here
        }
    }
        if(self.name === search)
        {
            self.matched = true;
            console.log(self.name);
        }
    
    return TreeNode;
}

I need to get this result: Search = 'two'
Result tree:

root - matched:false, expanded:true

left - matched:false, expanded:true

two - matched:true, expanded:false

Example
 * Original tree
 *       root
 *      |    \
 *    left  right
 *   |   |  \    \
 * one two three four
 *
 * Search = 'two'
 

 Result tree:
 *     root - matched:false, expanded:true
 *      |
 *    left - matched:false, expanded:true
 *      |
 *     two - matched:true, expanded:false

 Or if we describe it in JSON format
 Original tree
  {
  name: "root",
  expanded: false,
  matched: false,
  children: [
    {
      name: "left",
      expanded: false,
      matched: false,
      children: [
        {
          name: "one",
          expanded: false,
          matched: false,
          children: [],
        },
        {
          name: "two",
          expanded: false,
          matched: false,
          children: [],
        },
      ],
    },
    {
      name: "right",
      expanded: false,
      matched: false,
      children: [
        {
          name: "three",
          expanded: false,
          matched: false,
          children: [],
        },
        {
          name: "four",
          expanded: false,
          matched: false,
          children: [],
        },
      ],
    },
  ],
};
Result Tree:
{
  name: "root",
  expanded: true,
  matched: false,
  children: [
    {
      name: "left",
      expanded: true,
      matched: false,
      children: [
        {
          name: "two",
          expanded: false,
          matched: true,
          children: [],
        },
      ],
    },
  ],
}

Answer 1

I'm not sure what you (or your instructor) is looking for exactly, but we can do this in a more functional manner, without constructor functions or methods, with code something like this:

const treeNode = (name, children = []) => 
  ({name, children, expanded: false, matched: false})

const match = (query) => (
  {name, children: kids}, _, __, 
  children = kids .map (match (query)) .filter (n => n .matched || n.expanded)
) => ({
  name,
  children,
  expanded: children .length > 0,
  matched: name .toLowerCase () .includes (query .toLowerCase())
})

const tree = treeNode ("root", [treeNode ('left', [treeNode ('one'), treeNode ('two')]), treeNode ('right', [treeNode ('three'), treeNode ('four')])])


console .log ('Original tree', tree)
console .log ('Query "Two" result', match ('Two') (tree))
console .log ('Query "o" result', match ('o') (tree))
console .log ('Original tree is not modified', tree)

.as-console-wrapper {max-height: 100% !important; top: 0}

But the techniques may be beyond what you're supposed to be using for your course.

The factory function treeNode constructs a plain JSON object, in a similar manner to your constructor function (once you fix the self/this problem.)

match takes a query parameter and returns a function which takes your node, destructures it into name and children properties (we can safely ignore the others for now), aliasing kids for children, adds two blank parameters for technical reasons¹ and then create a children parameter by recurring on the node's children, and filtering to include only those that are themselves matched or which have matched descendants (and are therefore expanded.) We return a new object with the existing name property, the new list of children, and expanded flag set true if we have any children, and a matched flag if the current name matches the query parameter.

The base case for our recursion is slightly difficult to see. It happens when children is empty; at that point, we don't make deeper calls to match. And our recursive case is simply kids .map (match (query)).

We can certainly convert this to to something more OO, as needed. But I think this is simpler.

Update

I went ahead and tried an OO solution. It may seem more familiar to you.

class TreeNode {
  constructor (name, children = []) {
    this .name = name
    this .children = children
    this .expanded = false
    this .matched = false
  }
  
  match (query) {
    const children = this .children .map (c => c .match (query))
                          .filter (n => n .matched || n.expanded)
    const newNode = new TreeNode (this .name, children)
    newNode .expanded = children .length > 0
    newNode .matched = this .name .toLowerCase () .includes (query .toLowerCase())
    
    return newNode
  }
}

const tree = new TreeNode ("root", [new TreeNode ('left', [new TreeNode ('one'), new TreeNode ('two')]), new TreeNode ('right', [new TreeNode ('three'), new TreeNode ('four')])])

console .log ('Original tree', tree)
console .log ('Query "Two" result', tree .match ('Two'))
console .log ('Query "o" result', tree .match ('o'))
console .log ('Original tree is not modified', tree)

.as-console-wrapper {max-height: 100% !important; top: 0}

Update 2

What Bergi mentioned in the comments is that I'm using a fairly obscure, and in some ways horrible, hack to squeeze an extra value into the parameters so that I can code with pure expressions, rather than statements. (The reasons for that involve a long discussion.)

But if you want, this version may seem more familiar:

const match = (query) => ({name, children: kids}) =>  {
  const children = kids .map (match (query)) .filter (n => n .matched || n.expanded)
  return {
    name,
    children,
    expanded: children .length > 0,
    matched: name .toLowerCase () .includes (query .toLowerCase())
  }
}

It has the exact same behavior as my first sample.

Update 3

And now that I've mentioned that version, it probably makes sense to describe the other two versions I offered in the comments. One, using a really simple call helper,

const call = (fn, ...args) => fn (...args)

which we might write in either of two ways:

const match = (query) => ({name, children: kids}) => call ((
  children = kids .map (match (query)) .filter (n => n .matched || n.expanded)
) => ({
  name,
  children,
  expanded: children .length > 0,
  matched: name .toLowerCase () .includes (query .toLowerCase())
}))

or

const match = (query) => ({name, children: kids}) => call (
  (children) => ({
    name,
    children,
    expanded: children .length > 0,
    matched: name .toLowerCase () .includes (query .toLowerCase())
  }), 
  kids .map (match (query)) .filter (n => n .matched || n.expanded)
)

The second replaces that call function with an IIFE. And again, we can write it in either of two ways:

const match = (query) => ({name, children: kids}) => (((
  children = kids .map (match (query)) .filter (n => n .matched || n.expanded)
) => ({
  name,
  children,
  expanded: children .length > 0,
  matched: name .toLowerCase () .includes (query .toLowerCase())
})))()

or

const match = (query) => ({name, children: kids}) => (((children) => ({
  name,
  children,
  expanded: children .length > 0,
  matched: name .toLowerCase () .includes (query .toLowerCase())
}))) (kids .map (match (query)) .filter (n => n .matched || n.expanded))

Any of these version would do the same thing, and they all help with my boycott of statements. I'm partial to the first call version in my own work, but don't tend to use it in answers on SO because there is often confusion about the simple call function, confusion which distracts from the main points of the answers.

I do use the IIFE version, but the syntax can be distracting.

---

^{1This is so that we can pass the match(query) function to map, which supplies index and array parameters we don't need, but still default the additional children parameter.}

Answer 2

It's extremely rare for me to add a second answer to the same question, but the previous one, which has a number of interesting discussions and numerous edits, seems over-full. Here's another approach, which seems to capture a requirement that was missing in that earlier pass:

const treeNode = (name, children = []) => 
  ({name, expanded: false, matched: false, children})

const match = (query) => ({name, children: kids}, forced = false) => {
  const matched = name .toLowerCase () .includes (query .toLowerCase())
  const allChildren = kids .map (child => match (query) (child, forced || matched)) 
  const children = forced || matched ? allChildren : allChildren .filter (n => n .matched || n .expanded)
  const expanded = children .length > 0

  return {name, expanded, matched, children}
}

const tree = treeNode ("root", [treeNode ('left', [treeNode ('one'), treeNode ('two')]), treeNode ('right', [treeNode ('three'), treeNode ('four')])])

console .log ('Original tree', tree)
console .log ('Query "Two" result', match ('Two') (tree))  // two
console .log ('Query "o" result', match ('o') (tree))      // root, one, two, four
console .log ('Query "g" result', match ('g') (tree))      // right
console .log ('Original tree is not modified', tree)

.as-console-wrapper {max-height: 100% !important; top: 0}

We proceed as in Update 2 of that answer, with a simple functional approach, and with an imperative function body.

The substantive difference here is that we default an additional parameter to the function returned by match (query): the parameter force, which we default to false. This is used to decide whether we keep all children or only those that themselves either match or have a matching descendant. Before the recursive calls on the children, we check if our current node matches, and if so, set the new forced flag to true for those calls. This is to handle the phrase from the requirements I missed in the first answer:

Node is included in the resulting subtree if Node, one of its ancestors, or one of its descendants matches the search

If a node matches, then all of its descendants should be included. This handles that. This doesn't address the OP's comment on the previous answer that the code gets it wrong for the search of Two. As far as I can tell, this creates output identical to the sample, and that part of the logic should not have changed here.

AFAICT, modulo the change from a constructor to a factory function, this now matches all the requirements, except possibly this one:

returns TreeNode | null 

This will always return a treeNode object when supplied one. I'm not sure what null case here is meant to be considered. But we don't have one.

---

Since we delved into parameter handling on the earlier answer, maybe we should look at it here. This uses a technique which could lead to problems with calling code overriding our default parameter. If we're concerned by this, because it's possible that someone will call someArray .map (match ('Two')) or because we simply don't know how the function might be used, we can write a private implementation that uses that extra parameter, and supply it from a public wrapper function, like this:

const _match = (query) => ({name, children: kids}, forced) => {
  const matched = name .toLowerCase () .includes (query .toLowerCase())
  const allChildren = kids .map (child => _match (query) (child, forced || matched)) 
  const children = forced ? allChildren : allChildren .filter (n => n .matched || n.expanded)
  const expanded = children .length > 0
  return {name, expanded, matched, children}
}

const match  = (query) => (node) => 
  _match (query) (node, false)

---

Again, this should be straightforward to convert into an Object-Oriented style.

Update

Again, it seems relatively straightforward to convert to OO. This version should do it:

class TreeNode {
  constructor (name, children = []) {
    this .name = name
    this .expanded = false
    this .matched = false
    this .children = children
  }
  
  match (query, forced = false) {
    const matched = this .name .toLowerCase () .includes (query .toLowerCase())
    const allChildren = this .children .map (child => child .match (query, forced || matched)) 
    const children = forced || matched ? allChildren : allChildren .filter (n => n .matched || n .expanded)
    const newNode = new TreeNode (this .name, children)
    newNode .expanded = children .length > 0
    newNode .matched = matched
    
    return newNode
  }
}

const tree = new TreeNode ("root", [new TreeNode ('left', [new TreeNode ('one'), new TreeNode ('two')]), new TreeNode ('right', [new TreeNode ('three'), new TreeNode ('four')])])

console .log ('Original tree', tree)
console .log ('Query "Two" result', tree .match ('Two'))  // two
console .log ('Query "o" result', tree .match ('o'))      // root, one, two, four
console .log ('Query "g" result', tree .match ('g'))      // right
console .log ('Original tree is not modified', tree)

.as-console-wrapper {max-height: 100% !important; top: 0}

All we had to do is to take the body of match, make it a method, and convert all uses of the treeNode parameter (node, and children) into references to properties of this, and do the same for the recursive reference to match.

In doing this conversion, I noticed a bug when I tried an additional test case ('g'). It's fixed both in the original version and this one:

-   const children = forced ? allChildren : allChildren .filter (n => n .matched || n .expanded)
+   const children = forced || matched ? allChildren : allChildren .filter (n => n .matched || n .expanded)