Recursively Insert Element Into A Binary Tree

Question

So I finished my List exercise and went ahead with Binary Trees. My code thus far:

Tree.h

#include "Node.h"

class Tree
{
private:
    int mCount;
    Node *root;

public:
    Tree();
    ~Tree();

    void insert(int, Node *);
};

Tree.cpp

void Tree::insert(int data, Node *node)
{
    if( root == 0 )
    {
        Node *temp = new Node;
        temp->setData(100);
        temp->setRight(0);
        temp->setLeft(0);
        root = temp;
    }
    else
    {
        if( data > root->getData() )
            return insert( data, root->getRight() );
        else
            return insert( data, root->getLeft() );
    }
}

main.cpp

int main(int argc, char** argv)
{
    Tree *tree = new Tree;
    tree->insert( 100, 0 );

    std::cin.get();
    return 0;
}

I hope this is sufficient code. Node and Tree are two separate classes. I'm having difficulties wrapping my head around the recursion.

I have Node *root defined in my Tree class to have a root node at the top of the tree. However, the way I see it, when I call tree->insert insert in main, I don't have to specify any node. The root from the Tree class will do all the looking. However, when I'm in the code and need to recur, then I am suddenly a parameter short, as shown above.

My solution was to just place the parameter Node *node in the argument list for insert() anyway and call it with a 0 from main. I would also need to call tree->display(0); as parameter for Node *node as well.

This seems hackish. Am I missing something obvious?

Answer 1

A few points:

First, don't use Node**. That err "uglifies" your code. Use Node*& instead (see answers here) if you really need to.

Second, you do not need a recursive call (unless you want to use one).

Non-recursive insert method:

void Tree::insert(int data)
{
    if(!root)
    {
         root = new Node(data);  // Node constructor should receive
                                 // the data value and init internal value from it
                                 // it should also set left and right pointers to 0
         return;
    }

    Node* insertIterator = root;
    Node* parent = 0;

    while(insertIterator)
    {
         parent = insertIterator;
         insertIterator = data < insertIterator->getData() 
             ? insertIterator->getLeft()
             : insertIterator->getRight();
    }

    if(data < parent->getData())
         parent->setLeft( new Node(data) );
    else
         parent->setRight( new Node(data) );
}

If you do use a recursive method, use a recursive method that finds the insertion point, instead of a recursive method that performs the insertion. Basically, replace the while loop in the code above with a separate method (FindInsertionPoint in my code below):

Node* Tree::FindInsertionPoint(int data, Node * parent) // this should be private
{
    Node* insertPoint = data < parent.getData()
        ? parent->getLeft() 
        : parent->getRight();

    return insertPoint
        ? FindInsertionPoint(data, insertPoint)
        : parent;
}

void Tree::Insert(int data)  // this should be public
{
    if(!root)
    {
        root = new Node(data);
        return;
    }

    Node* parent = FindInsertionPoint(data, root);
    if(data < parent.getData())
        parent->setLeft(new Node(data)); // see comment on Node constructor above
    else
        parent->setRight(new Node(data)); // see comment on Node constructor above
}

Edit:

I'm having difficulties wrapping my head around the recursion.

Look at it like this: to find the insertion point, you know that you need to insert as a child of the left or the right subnode. To insert to the left, you need to insert as a child of the left or the right subnode of the left child of the current node. That is, if you insert to the left, call the find the insertion point part for the left child; otherwise, call the find the insertion point for the right subnode.

What you need to do to define a recursive algorithm:

• identify the algorithm as it applies to a part of your data (in this case, you need to insert as a child of the left or the right subnode).

• identify the stopping condition (when is the algorithm stopping?). If you do not, you get infinite recursion and a stackoverflow error :).

• identify the variable part of the algorithm (this should tell you what parameters your recursive function will have).

Answer 2

You are currently not using the node parameter at all in Tree::insert, which effectively means that it will recurse infinitely if you already have a root node.

The best solution would be to define a public insert method without node parameter, which calls another, private insert method with the root parameter, which in turn recursively calls itself. This way your API is clean, not allowing its clients to insert elements directly (and incorrectly) into subtrees.

Note that the parameter itself must be changed to Node** Node*&, since at the point of insertion, you want to modify the pointer in the parent node.

[Update] Also it would be recommended to add a constructor to Node which takes the data value and initializes its left and right pointers to 0. This simplifies the caller code noticeably. [/Update]

So the final result would look something like this:

void Tree::insert(int data)
{
    return insert( data, root );
}

void Tree::insert(int data, Node *&node)
{
    if( node == 0 )
    {
        node = new Node(data);
    }
    else
    {
        if( data > node->getData() )
            return insert( data, node->getRight() );
        else
            return insert( data, node->getLeft() );
    }
}