CODEWITHSUNDEEP
c++pointersbinary-search-treenodes
leite0407
leite0407

Reputation: 31

BST - node getting mysteriously getting assigned to wrong side

I wrote this: 

#include <stdio.h>
#include <string.h>

struct node {
    int value;
    bool right;
    bool left;
    node * rightChild;
    node * leftChild;
};

int insertNode(int value, node* parent, int h) {
    if (value < parent->value) {
        if (!parent->left) {
            node temp = {value, NULL, NULL};
            parent->leftChild = &temp;
            parent->left = true;
            return h + 1;
        }

        return insertNode(value, parent->leftChild, h + 1);
    }
    if (value > parent->value) {
        if (!parent->right) {
            node temp = {value, NULL, NULL};
            if (value == 1)
                printf("here\n\n");
            parent->rightChild = &temp;
            parent->right = true;
            return h + 1;
        }
        return insertNode(value, parent->rightChild, h + 1);
    }
}



int main() {

    int N; scanf("%d", &N);

    int values[N];

    for (int i = 0; i < N; i++)
        scanf("%d", &values[i]);

    node base = {values[0], false, false, NULL, NULL};
    printf("0\n");
    int counter = 0;

    for (int i = 1; i < N; i++) {
        int height = insertNode(values[i], &base, 0);
        counter += height;
        printf("%d\n", counter);
    }
}

So, I made this program and what it's supposed to do is build a BST from input, keep a counter with the sum of the heights of each node and output the value of that counter every time a node is inserted.

For most test cases, it works just as it should but for this test case it doesn't output what it is supposed.

Input : 8 3 5 1 6 8 7 4 2
Expected Output: 0 1 2 4 7 11 13 15
Obtained Output: 0 1 2 4 7 11 14 18

I traced down the error and it looks like somehow 1 is inserted both as the right child of 3 and left child of 3 and 5 is not inserted into the tree There's only one condition in the code where a node is set as another node's right child and I checked and 1 never falls into that condition. How's that possible?

I'm honestly going crazy with this right now, can someone please help me understand what I'm doing wrong

Upvotes: 0

Views: 26

Answers (1)

Lightness Races in Orbit
Lightness Races in Orbit

Reputation: 385295

node temp = {value, NULL, NULL};
if (value == 1)
    printf("here\n\n");
parent->rightChild = &temp;

Think about what then happens to temp (it goes out of scope), then think about what happens to parent->rightChild as a result (it becomes a dangling pointer). Any subsequent access to that pointer results in your program having undefined behaviour, hence apparently random results.

You need to dynamically allocate your node objects, so that you can control their lifetime yourself (including extending them beyond that little block scope). Any good example of a BST implementation should show this.

Upvotes: 1

Related Questions