CODEWITHSUNDEEP
javascriptalgorithmrecursiontree
user1261710
user1261710

Reputation: 2639

JavaScript - How can I return the branch of a tree in a node search?

My data structure will look like this:

var tree = [
    {
        id: 1,
        children: []
    }, {
        id: 2,
        children: [
            {
                id: 3,
                children: []
            }
        ]
    }
];

There can be any number of nodes or children on one branch.

My goal is to start at the top (root) node, search for a given node and return the branch it's on.

So in the example on Plunker: https://plnkr.co/edit/PyR3H7mM0vrFyno1l7R5?p=catalogue

I want to search for the node id # 31, so the algorithm will return the array (branch) that 31 is a part of.

I have started the algorithm but if I do it recursively I don't know how to backtrack out again.

function traverse(branch) {

  for (var i = 0; i < branch.length; i++) {
    if (branch[i].id == node.id) {
      return branch;
    }
  }

  for (var j = 0; j < branch.length; j++) {
    if (branch[j].children.length > 0) {
      return traverse(branch[j].children);
    }
  }

}

console.log(traverse(tree));

For example, if I look down to the last child node without finding a match then I need to backtrack to the parent branch to try the next set of options.

How can I modify my algorithm to backtrack out again?

Upvotes: 1

Views: 2267

Answers (3)

user1261710
user1261710

Reputation: 2639

This did the trick to return the branch rather than the node itself:

    function traverse(branch) {

        for (var i = 0; i < branch.length; i++) {
            if (branch[i].id == node.id) {
                return branch[i].children;
            }
        }

        for (var j = 0; j < branch.length; j++) {
            var result = traverse(branch[j].children);
            if (result !== null) {
                return result;
            }
        }

        return null; // no match found
    }

Upvotes: 0

Nina Scholz
Nina Scholz

Reputation: 386776

You could use an temporary variable for the result of the children and exit the loop if the value is truthy.

function traverse(branch) {
    var result;
    for (var i = 0; i < branch.length; i++) {
        if (branch[i].id === node.id) {
            return branch;
        }
        if (branch[j].children.length > 0) {
            result = traverse(branch[j].children);
            if (result) {
                return result;
            }
        }
    }
}

Upvotes: 1

castletheperson
castletheperson

Reputation: 33496

Your algorithm is very close, you just need to add an if statement so that it only returns the recursive result from traverse if a match was found:

function traverse(branch) {

  for (var i = 0; i < branch.length; i++) {
    if (branch[i].id == node.id) {
      return branch;
    }
  }

  for (var j = 0; j < branch.length; j++) {
    var result = traverse(branch[j].children);
    if (result !== undefined) {
      return result;
    }
  }

  return undefined; // no match found

}

console.log(traverse(tree));

Upvotes: 2

Related Questions