CODEWITHSUNDEEP
javascripttypescriptrecursiontree
tom
tom

Reputation: 2357

Finding the objects in a tree of objects between the root and any object

I have a typical tree data structure that looks like this:

[
  {
    data: object,
    subs:
      [ ...other objects... ]
  },
  ...other objects...
]

It can have any shape and number of nodes.

I wrote a method that should recursively find and return the path (an array of intermediate objects) between the root r and a given object o. (whether or not including r and o I don't care)

public getPath(tree: Array<object>, o: object): Array<object> {

  let path: Array<object> = [];

  function f(subtree: Array<object>): void {
    for (let node of subtree) {

      path.push(node['data']);
      if (node['data'] == o) return;
      else if (node['subs'].length > 0) f(node['subs']);
      else path = [];

    }
  }

  f(tree);
  return path;

}

Basically my idea was to

Results:

Upvotes: 2

Views: 229

Answers (1)

ibrahim mahrir
ibrahim mahrir

Reputation: 31692

The flaw with your code is that you are using a global (out of f's scope anyway) path array. The problem is that you are clearing the entire array if a node doesn't match, whereas you should only cut the current part out. There are two ways to achieve what you want: first is to make f accepts an array path that it copies and pass over recursively untill it find the object, and the other way which is the best approach is to make use of the call stack (created by the recursion):

public getPath(tree: Array<object>, o: object): Array<object> {

    function f(subtree: Array<object>) {                              // I don't know typescript, so specify the return type as (Array<object> or null)
        for (let node of subtree) {
            if (node.data == o) {                                     // if this is the node we're looking for
                return [node];                                        // return an array (which will be our path), here you can either return [] to exclude the matched node (o) or [node] to include it
            } else if(node.subs.length) {                             // not the node we are looking for, but it has children, so let check'em out 
                let result = f(node.subs);                            // result will either be an array (if we recursively found something), or null otherwise
                if(result) {                                          // if we found something, then result will be the path from the current node to the object o (the current node not included)
                    result.unshift(node);                             // we include the current node by pushing it into the result array (pushing it to the first position)
                    return result;                                    // return result (an array) to signal successfulness
                }
            }
        }
        return null;                                                  // the object o not found in this subtree, return null to signal unsuccessfullness. Kind of redundant, because undefined is returned by default, so feel free to remove it
    }

    return f(tree);    
}

Upvotes: 2

Related Questions