Understanding pointers in binary tree

Question

I'm new to C++ and I normally use Java, so I have a hard time to get into pointers and references. I have to do a variation of binary search tree with inner nodes and leaf nodes (only leafs contain the data).

class Node
    Node *parent;
    Node *left;
    Node *right;
    //other stuff
}

I need to implement operator<< which adds a new node with value to the tree.

//adding a node to tree
void operator<<(int value){
    if(size == 0){
        //stuff
    } else {
        Node* temp = root;
        getLeaf(temp,value);  
        //other magic        
        //temp will be used to append a new node into tree, 
        //so it has to point to the actual node in the tree
        delete temp;
    }        
}

The point of function getLeaf is to find a leaf (may or may not contain the desired value) and store it into temp, which needs to be accessible in the operator<< function.

int getLeaf( Node* temp, int value) const{
    int depth = 0;
    //goes trough all inner nodes until it finds specific leaf
    while(temp->isInner()){
        ++depth;
        if(value < temp->getValue()){ //searched value is smaller
            temp = temp->getLeft(); // to left subtree
            continue;
        } else {
            temp = temp->getRight(); //to rightsubtree
            continue;
        }
     return depth;
}

I am really confused how to do this and what is the right combination of pointers and values. If I set

    Node* temp = root;
    getLeaf(temp,value);  

won't root get overridden while traversing the tree in getLeaf function?

Plus I need temp to point to actual node in the tree, so I can append a new node into it.

Could you please explain?

Answer 1

Migrating from Java to C++ is a bit tough. Migrating from C++ to Java is equally tough. To make things easy you just need to experiment.

In C++, pointers are variables that point to the location of another variable in memory and references are pointers that syntactically behave like the variable whose address is pointed to.

When arguments are passed to a function, the function does NOT receive the original arguments but a copy of them. The work you did is implement the traversal based on the above concepts. So how does it all "magically" work?

Your function: getLeaf(Node *&temp, int value) searches the correct leaf node and assigns it to temp at which insertion is to be performed. temp here is a copy of a reference to the pointer temp(in operator <<). So when the reference temp is assigned to in getLeaf, the pointer temp in operator << it points to is modified.

If I set

Node *temp = root;
getLeaf(temp,value);

won't root get overriden while traversing the tree in getLeaf function?

Note here that temp and root are two different pointers that point to the same variable. The content of the pointers is the same, they aren't and hence root is NOT overridden, when temp is updated.

But there is a problem later on in the code. If you delete temp;, root will also be deleted at the end of insertion as delete deletes the content pointed to by the pointer. Do NOT delete a pointer that is not allocated by a new.

Provide a separate function to free the dynamically allocated memory used by the tree, and call it at the end when you are done experimenting.