Binary Tree Implementation C++

Question

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){
        ??????
    }
}

Answer 1

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();
}