CODEWITHSUNDEEP
c++recursiontree
Kajzer
Kajzer

Reputation: 2385

Strange return behaviour in recursive function

I have a tree node class like this:

class Node
{
public:
    Node();
    Node(char _value);
    ~Node();

    char getValue() const;
    Node* getParent() const;
    void addChild(Node* _child);
    bool isLeaf() const;
    bool isRoot() const;
    bool hasChild(char _value) const;
private:
    vector<Node*> children;
    char value;
    Node* parent;
};

And I have a serach method implemented:

bool Node::hasChild(char _value) const
{
    if (value == _value)
        return true;

    for (auto it = children.begin(); it != children.end(); it++)
    {
        if (*it != NULL)
        {
            (*it)->hasChild(_value);
        }
    }
}

However, when I run this code, the tmp variable is always false. If I trace it with a debugger, the return true; part executes, but the recursion continues. Any tips?

Node* root = new Node();
Node* a = new Node('a');
Node* c = new Node('c');

root->addChild(a);
root->addChild(c);

bool tmp = root->hasChild('a');

Upvotes: 0

Views: 96

Answers (2)

paxdiablo
paxdiablo

Reputation: 881273

Your problem lies in hasChild In the way it calls itself:

(*it)->hasChild(_value);

You call it but do not do anything with the return value. You may want to try returning the result.

Since it appears your algorithm indicates a non-sorted tree, that's not as easy as just prefixing the statement with return. You probably need to check for true and return it but false means keep looking:

if ((*it)->hasChild(_value))
    return true;

You also need to return false at the end of the function.

Upvotes: 3

Nicholas Betsworth
Nicholas Betsworth

Reputation: 1793

Your code for hasChild has two major flaws, it is never able to return false, and the return value of your call to hasChild at the following lines is never utilised:

(*it)->hasChild(_value);

This should resolve your issue (bar any issue with the rest of the code)

Upvotes: 4

Related Questions