CODEWITHSUNDEEP
c++binary-tree
user1870035
user1870035

Reputation:

Binary Tree Implementation C++

I've been trying to implement a binary search tree in C++ for fun. My problem is that I'm having trouble with my insert function. Below is what I have so far:

Header

class TreeNode{
public: 
    int data;          
    TreeNode *left;    
    TreeNode *right;  
    void Insert(int value, TreeNode *x);
    void TreeNode::Print(TreeNode *x);
    TreeNode();
};


TreeNode::TreeNode(){
    left = NULL;
    right = NULL;
}

Source

void TreeNode::Insert(int value, TreeNode *x){
    if(x->left == NULL && x->right == NULL){
        TreeNode *tree = new TreeNode();                        
        tree->datavalue;                                  
        x->left = tree;                                  
    }
    else if(x->left == NULL && x->right != NULL){
        TreeNode *tree = new TreeNode();                
        tree->data = value;                         
        x->left = tree;                                 
    }
    else if(x->left != NULL && x->right == NULL){
        TreeNode *tree = new TreeNode();                      
        tree->data = value;                            
        x->right = tree;                          
    }
    else if(x->left != NULL && x->right != NULL){
        ??????
    }
}

Upvotes: 2

Views: 3465

Answers (2)

JustinDanielson
JustinDanielson

Reputation: 3185

You should not insert blindly, follow the logic below. If x.value is less than the root value, attempt to insert to the left. If x.value is >= root.value, go to the right. Repeat this logic until you hit a NULL value. That will be the proper place to insert your element.

You could flip the logic, I just chose left on < because less than kinda makes an arrow to the left. <- :P

TreeNode *root = this;
TreeNode *parent = root;
//Traverse the tree, go left if x.val < , else go right(>=)
while(root) {
    parent = root;
    root = (root->value > x.value) ? root->left : root->right;
}
if(parent->value > x->value) 
    parent->left = x;
else
    parent->right = x;

If you don't care about ordering, do a depth first search with a Queue.

queue<TreeNode*> nodes;
nodes.push(this);
while(1)
{
    if(!nodes.front()->left)
    {
        nodes.front()->left = x;
        return;
    } 
    else if (!nodes.front()->right)
    {
        nodes.front()->right = x;
        return;
    }
    nodes.push(nodes.front()->left);
    nodes.push(nodes.front()->right);
    nodes.pop();
}

Upvotes: 5

h4ck3d
h4ck3d

Reputation: 6364

If you want to insert when both left and right child are NOT null , then you can insert the item by recursively moving to the left-most node of the tree. And since you are just inserting values in no particular order , it will be difficult to keep track. Rather implement a Binary Search Tree in that case.

else if(x->left != NULL && x->right != NULL){
         Insert(value,x->left);
         x-> data  = value;
         x->left = x->right = NULL;
}

And most importantly , insert a BASE case to exit from recursion.

Upvotes: 0

Related Questions