CODEWITHSUNDEEP
c++c++11recursiondata-structurestree
William Schaffer
William Schaffer

Reputation: 35

Searching a General Tree? Function is stopping at end of tree instead of searching the next branch

I have a general tree where the root's children are stored in a linked list as follows:

class node
{
    int identifier;
    node *parent;
    std::vector<node *> children;

I am trying to implement a function that will search the tree and either return a pointer to the node whose int identifier matches the key to search for or nullptr if no match is found. Here is how I think it should work:

  1. If the current node -> identifier == identifier, return the current node.
  2. Otherwise, if the node has no children, return nullptr.
  3. Loop through the list of children, and recursively call and return find(int identifier) on each child.
  4. If no match is found, return nullptr.

Here is the tree being used for the unit test:

1-\
|-2-\
|   |-3
|   |-4
| 
|-5-\
|    |-6-\
|    |    |-7
|    |-8
|    |-9

It appears to be executing correctly for find(1), find(2), and find(3), however, find(4) is finishing at node 3 instead of stopping at 3, going back to 2, and then trying the "4" branch.

Looking for help figuring out what I need to do to get it to go to the next branch instead of finishing when the branch has no more children. Thanks for looking everyone.

Code:

node* node::find(int identifier)
{
    cout << "FIND: " << identifier << endl;
    cout << "this->identifier: " << this->identifier << endl;
    if (this->identifier == identifier) return this;
    if (this->children.empty()) return nullptr;
    for (node* child : this->children) return child->find(identifier);
    return nullptr;
}

Upvotes: 0

Views: 187

Answers (1)

Abel
Abel

Reputation: 489

check if the child returned null before you return it

node* childfound;
for (node* child : this->children){
childfound = child->find(identifier);
if(childfound) return childfound;
}

Upvotes: 1

Related Questions