CODEWITHSUNDEEP
algorithmrecursionsearchtree
Tim Mitchell
Tim Mitchell

Reputation: 653

Is there a good recursive algorithm for finding a value in a tree?

I have a tree data structure in which I would like to determine if a value exists in one of the nodes.

The tree isn't a binary tree; each node may have an unlimited number of child nodes.

I would like to do a recursive algorithm such that as soon as the value is found, a true value is returned. And if every node is visited without finding the value, a false value is returned.

This is turning out to be a little tougher than I thought. I can visit every node - but I'm unsure when to return a false value.

Here is my psuedo-code:

boolean doesValueExist(tree, value) {

    for (int ii=0; ii<tree.numChildren; ii++) {
        if (tree.getChild(ii).value = value) {
            return true;
        }
        return doesValueExist(tree.getChildren());
    }

    //When do a return a false value?
}

Thank you

Upvotes: 0

Views: 81

Answers (2)

Tim
Tim

Reputation: 833

Thank you - I do appreciate it.

I'm trying to give you credit. For some reason the accept icon isn't appearing.

Upvotes: 1

Maras
Maras

Reputation: 982

I'd do something like that (which is basically a graph traversal on a tree):

 boolean doesValueExist(tree, value) {
      // value found in the current node
      if(tree.value == value) {
             return true;
      }

      for (int ii=0; ii<tree.numChildren; ii++) {
             //the value found in one of the subtrees
             if (doesValueExist(tree.getChild(ii), value) {
                 return true;
             }
       }

       //the value was not found in any subtree
       return false;
  }

Upvotes: 1

Related Questions