How to recursively call a recursive function? (AVL/BST tree)

[drmario6532]

For this project, search all the nodes to see if the username key is the same as the node's username, then insert the object into the node. If no node is found, it has to be created.

I've created a function that will tell me if the node containing the same username is somewhere in the tree. I want to call it to my other insert function, but right now, it's only printing one of the values. I think it's because I'm not calling it recursively.

How would I change this function so that it calls the other recursive function multiple times?

[salem c]

Perhaps

bool Tree::isFound(Node*& node, string user) {
   if ( node != nullptr ) {
         if (user < node->getUser()){
             return isFound(node->_right,user);
         }
         else if(user > node->getUser()){
             return isFound(node->_left,user);
         }
         else{
             return true;
         }
   } else {
      return false;
   }
}

[dhayden]

In the original post, you're passing node by reference. At lines 4 and 7, you modify the node, which means you modify the node that was passed in. This is almost certainly a bug.

It's a little hard to wrap your head around at first, but a really helpful function for dealing with a tree is :
// Search the subtree for "user". If found, return a reference to the pointer to the node.
// If not found, return a reference to the pointer where it should be inserted.

Node *& Tree::findPos(Node *& parent, const string &user)
{
    if (parent == nullptr) return parent;

    if (user < parent->getUser()) {
        return findPos(parent->left, user);
    } else if (user > parent->getUser()) {
        return findPos(parent->right, user);
    } else {
        return parent;
    }
}

In the real world you'd probably do this with a loop instead of recursion, but you asked about recursion.

With this, insert is simple:

    void Tree:insert(const string &user) {
        Node * &parent = findPos(root, user);
        if (parent == nullptr) {
            parent = new Node();
            parent->user = user;
        }
    }