CODEWITHSUNDEEP
c++recursionbinary-treeinsertion
HJM
HJM

Reputation: 236

Binary Search Tree Insertion C++ rooted at current node

I need to add an item to a binary tree given only the item to be added.

Here is the code I'm given:

void BinaryTree::add(Data * data) {
    if (root == NULL) {
        root = new BinaryTreeNode(data);
    }
    else {
        root->add(data);
    }
}

where root is a private variable of a BinaryTree defined as a BinaryTreeNode.

I need to implement a method:

void BinaryTreeNode::add(Data * data);

where a BinaryTreeNode is:

class BinaryTreeNode {
public:
    Data * nodeData;
    BinaryTreeNode * left;
    BinaryTreeNode * right;

    /**
     * Constructor
     */
    BinaryTreeNode(
        Data * data,
        BinaryTreeNode * left = NULL,
        BinaryTreeNode *right = NULL
    )
      : nodeData(data), left(left), right(right)
    { }

    // ...

I want to do this recursively, but I'm not positive how when you're only passed the data to be added.

My idea that doesn't work is:

void BinaryTreeNode::add(Data * newData) {
    BinaryTreeNode * temp = this;
    if (temp == NULL) {
        temp->nodeData = newData;
    } else {
        if (newData->compareTo(nodeData) < 0) {
            temp->left->add(newData);
        } else {
            temp->right->add(newData);
        }
    }
}

Upvotes: 0

Views: 520

Answers (2)

vishakvkt
vishakvkt

Reputation: 864

Well a binary tree, atleast how I know how to implement involves something like the following with two objects, one containing the the treenode object, and the other acting as an interface for the whole tree.

 class cBinaryTree {

 public:
 bool insert(int inData);
 //Other operations

 private:
 cBinaryTreeNode* root;
 bool leftInsertion;
 cBinaryTreeNode* getRoot() { return root; }

As you are comparing the actually value of the input data and placing it accordingly, this qualifies as a binary search tree. Then the insertion function can be written as

bool cBinaryTree::insert(int inData) {

//handle case if its first node.
cBinaryTreeNode *Parent = getInsertionNodePosition(getRoot(), inData);
cBinaryTreeNode *newNode = createNewNode(inData);

if(leftInsertion) //insert into left. add return statement
    Parent->setLeftChild() = newNode;
else //insert into right 
}

The recursive lookup function will be something like

cBinaryTreeNode* getInsertionNodePosition(cBinaryTreeNode* node,int inData) {

//Check left subtree and proceed from there.
if(inData < node->getData()) {
    if(node->getLeftChild() == NULL)  {             
        leftInsertion = true;
        return node;
    }
    else {
        node = node->getLeftChild();
        return getInsertionNodePosition(node, inData);
    }
}
    //Similarly Check right subtree.

Hope this helps.

Upvotes: 0

Vaughn Cato
Vaughn Cato

Reputation: 64308

You are setting temp to this and then comparing it to NULL. this should never be NULL. You need to check if the left and right are NULL.

Upvotes: 2

Related Questions