BST Insert C++ Help

typedef struct treeNode {
    treeNode* left;
    treeNode* right;
    int data;
    treeNode(int d) {开发者_开发知识库
        data = d;
        left = NULL;
        right = NULL;
    }
}treeNode;

void insert(treeNode *root, int data) {
    if (root == NULL) {
        cout << &root;
        root = new treeNode(data);
    }
    else if (data < root->data) {
        insert(root->left, data);
    }
    else {
        insert(root->right, data);
    }
}

void inorderTraversal(treeNode* root) {
    if (root == NULL)
        return;
    inorderTraversal(root->left);
    cout<<root->data;
    inorderTraversal(root->right);
}

int main() {
    treeNode *root = new treeNode(1);
    cout << &root << endl;
    insert(root, 2);
    inorderTraversal(root);

    return 0;
}

So I'm pretty tired, but I was whipping some practice questions up for interview prep and for some reason this BST insert is not printing out that any node was added to the tree. Its probably something im glossing over with the pointers, but I can't figure it out. any ideas?

---

void insert(treeNode *root, int data) {
   if (root == NULL) {
   cout << &root;
   root = new treeNode(data);
}

This change to root is lost as soon as the function ends, it does not modify the root passed as argument but its own copy of it.

---

Take note that when u insert the node, use pointer to pointer (pointer alone is not enough): So, here is the fixed code:

void insert(treeNode **root, int data) {
    if (*root == NULL) {
        cout << root;
        *root = new treeNode(data);
    }
    else if (data < (*root)->data) {
        insert(&(*root)->left, data);
    }
    else {
        insert(&(*root)->right, data);
    }
}

And in main:

int main() {
    treeNode *root = new treeNode(1);
    cout << &root << endl;
    insert(&root, 2);
    inorderTraversal(root);

    return 0;
}

---

Your logic is correct!

The only issue is that when you create a local variable, even if it is a pointer, its scope is local to the function. In your main:

...
insert(root, 2);
...

function call sends a copy of the root which is a pointer to treeNode (not the address of root). Please note that

void insert(treeNode *root, int data)

gets a treeNode pointer as an argument (not the address of the pointer). Attention: This function call may look like "call by pointer" (or reference) but it is actually "call by value". The root you define in the main function and the root inside the insert method have different addresses in the stack (memory) since they are different variables. The former is in main function stack in the memory while the latter is in insert method. Therefore once the function call insert finishes executing, its stack is emptied including the local variable root. For more details on memory refer to: stacks/heaps.

Of course the data in the memory that you allocated using:

*root = new treeNode(data);

still stays in the heap but you have lost the reference to (address of) it once you are out of the insert function.

The solution is either passing the address of original root to the function and modifying it (as K-ballo and dip has suggested) OR returning the modified local root from the function. For the first approach please refer to the code written by dip in his/her answer.

I personally prefer returning the modified root from the function since I find it more convenient especially when implementing other common BST algorithms. Here is your function with a slight modification of your original code:

treeNode* insert(treeNode *root, int data) {
    if (root == NULL) {            
        root = new treeNode(data);
    }
    else if (data < root->data) {
        root->left=insert(root->left, data);
    }
    else {
        root->right=insert(root->right, data);
    }

    return treeNode;
}

The function call in main will be:

int main() {
    treeNode *root = new treeNode(1);
    cout << &root << endl;
    root = insert(root, 2);
    inorderTraversal(root);

    return 0;
}

Hope that helps!

---

After a while seeing some complicated methods of dealing with the Binary tree i wrote a simple program that can create, insert and search a node i hope it will be usefull

/*-----------------------Tree.h-----------------------*/
#include <iostream>
#include <queue>

struct Node
{
    int data;
    Node * left;
    Node * right;
};
// create a node with input data and return the reference of the node just created
Node* CreateNode(int data);

// insert a node with input data based on the root node as origin
void InsertNode (Node* root, int data);

// search a node with specific data based on the root node as origin
Node* SearchNode(Node* root, int data); 

here we define the node structure and the functions mentioned above

/*----------------------Tree.cpp--------------*/
#include "Tree.h"

Node* CreateNode(int _data)
{
 Node* node = new Node();
 node->data=_data;
 node->left=nullptr;
 node->right=nullptr;
 return node;
}

void InsertNode(Node* root, int _data)
{
// create the node to insert
 Node* nodeToInsert = CreateNode(_data);

// we use a queue to go through the tree
 std::queue<Node*> q;
 q.push(root);


while(!q.empty())
{
    Node* temp = q.front();
    q.pop();

    //left check
    if(temp->left==nullptr)
    {
        temp->left=nodeToInsert;
        return;
    }
    else
    {
        q.push(temp->left);
    }

    //right check
    if(temp->right==nullptr)
    {
        temp->right=nodeToInsert;
        return;
    }
    else
    {
        q.push(temp->right);
    }
}


}


Node* SearchNode(Node* root, int _data)
{
 if(root==nullptr)
    return nullptr;

std::queue<Node*> q;
Node* nodeToFound = nullptr;
q.push(root);
while(!q.empty())
{
    Node* temp = q.front();
    q.pop();
    if(temp->data==_data) nodeToFound = temp;
    if(temp->left!=nullptr) q.push(temp->left);
    if(temp->right!=nullptr) q.push(temp->right);
   
}


return nodeToFound;
}
int main()
{
// Node * root = CreateNode(1);
// root->left = CreateNode(2);
// root->left->left = CreateNode(3);
// root->left->left->right = CreateNode(5);
// root->right = CreateNode(4);

// Node * node = new Node();
// node = SearchNode(root,3);
// std::cout<<node->right->data<<std::endl;
return 0;
}