1

Here's a simple binary search tree (BST) that I cooked up to illustrate my problem

struct BST {
    int key;
    BST *left, *right;
};

Here's a function that inserts a node into the BST:

bool insert (BST *root, BST *node) {
    // base case. Do the insertion 
    if (root == nullptr) {
        root = node;
        return true;
    }
    if (root->key < node->key)
        insert(root->left, node);
    else
        insert(root->right, node);
}

And here's my int main:

int main () {
    // Make a root for the BST
    BST root = {10, nullptr, nullptr};
    BST *root_p = &root;

    // Insert node into BST
    BST node = {5, nullptr, nullptr};
    BST *node_p = &node;
    insert(root_p, node_p);

    // Should see the address of the inserted node
    cout << root_p->left << endl;  // it outputs 0 (nullptr). Why?

}

I'm trying to do an insertion on the BST. I first initialized the root and then a pointer to the root called root_p. Any insertions in the BST would take place from the root_p. I then tried inserting a new node into the BST.

Ideally, insert(root_p, node_p) should have caused root_p's left pointer to have the value of node_p (following BST conventions where left child's key is smaller). However, that doesn't happen and instead root_p's left pointer is still a nullptr. Why is that so? Any help is appreciated!

PS: I tried changing insert to take a ref to the pointer instead (i.e. BST *&root), but that yields identical results.

babrar
  • 179
  • 2
  • 14
  • 1
    For why the reference change didn't work: You use `if (root->key < node->key) insert(root->left, node);` but `left` should be populated when `root->key` is greater than `node->key`, not less than. Fix that and you'll get the expected results. – NathanOliver Mar 11 '20 at 16:35

0 Answers0