0

I have written a code which performs some basic operations on binary search tree. My code runs perfectly on linux ecosystems like Ubuntu or WSL2 but gives incorrect output in windows ecosystem more specifically Windows 10. Here's my code


#include <stdio.h>
#include <malloc.h>

typedef struct TreeNode
{
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

typedef struct node
{
    TreeNode *data;
    struct node *next;
} node;

typedef struct queue
{
    node *head;
    node *tail;
    int size;
} queue;

TreeNode *insert_in_bst(int element, TreeNode *root);
TreeNode *delete_in_bst(int element, TreeNode *root);
void inorder(TreeNode *root);
void levelwise(TreeNode *root);
void enqueue(queue *q, TreeNode *root);
node *dequeue(queue *q);
void mirror_image(TreeNode *root);
int height(TreeNode *root);

int main(int argc, char *argv[])
{
    int n = 0;
    printf("Enter elements to be added to bst - ");
    scanf("%d", &n);
    TreeNode *root;
    while (n != -1)
    {
        root = insert_in_bst(n, root);
        scanf("%d", &n);
    }
    levelwise(root);
    printf("\nCurrent inorder - ");
    inorder(root);
    int del;
    printf("\nEnter element to delete - ");
    scanf("%d", &del);
    delete_in_bst(del, root);
    levelwise(root);
    printf("\nNew inorder - ");
    inorder(root);
    printf("\nMirror image\n");
    mirror_image(root);
    levelwise(root);
    int h = height(root);
    printf("\nHeight = %d", h);
    return 0;
}

TreeNode *insert_in_bst(int element, TreeNode *root)
{
    if (!root)
    {
        TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
        newNode->data = element;
        return newNode;
    }

    if (element < root->data)
    {
        root->left = insert_in_bst(element, root->left);
    }
    else
    {
        root->right = insert_in_bst(element, root->right);
    }

    return root;
}

TreeNode *delete_in_bst(int element, TreeNode *root)
{
    if (!root)
        return NULL;

    if (element < root->data)
    {
        root->left = delete_in_bst(element, root->left);
    }
    else if (element > root->data)
    {
        root->right = delete_in_bst(element, root->right);
    }
    else
    {
        if (!root->left)
            return root->right;
        else if (!root->right)
            return root->left;
        else
        {
            TreeNode *curr = root->right;
            while (!curr->left)
                curr = curr->left;
            root->data = curr->data;
            root->right = delete_in_bst(curr->data, root->right);
        }
    }
    return root;
}

void inorder(TreeNode *root)
{
    if (!root)
        return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

void levelwise(TreeNode *root)
{
    node *currNode = (node *)malloc(sizeof(node));
    currNode->data = root;
    queue *q = (queue *)malloc(sizeof(queue));
    enqueue(q, root);
    while (q->size != 0)
    {
        int l = q->size;
        for (int i = 0; i < l; i++)
        {
            node *temp = dequeue(q);
            TreeNode *t = temp->data;
            printf("%d ", t->data);
            if (t->left)
            {
                enqueue(q, t->left);
            }
            if (t->right)
            {
                enqueue(q, t->right);
            }
        }

        printf("\n");
    }
}

void enqueue(queue *q, TreeNode *root)
{
    node *temp = (node *)malloc(sizeof(node));
    temp->data = root;
    if (!q || !q->head)
    {
        q->head = temp;
        q->tail = temp;
        q->size = 1;
    }
    else
    {
        q->tail->next = temp;
        q->tail = q->tail->next;
        q->size++;
    }
}

node *dequeue(queue *q)
{
    node *top = q->head;
    q->head = q->head->next;
    q->size--;
    return top;
}

void mirror_image(TreeNode *root)
{
    if (!root)
        return;

    TreeNode *temp = root->left;
    root->left = root->right;
    root->right = temp;
    mirror_image(root->left);
    mirror_image(root->right);
}

int height(TreeNode *root)
{
    if (!root)
        return 0;
    int lh = height(root->left);
    int rh = height(root->right);

    return 1 + (lh > rh ? lh : rh);
}

Heres the output on Windows ecosystems

Here's the output on linux/wsl2

On further debugging on Windows systems, i found out that by default; value to root is assigned as 1. On linux systems this thing doesnt happen. Can someoe help me find out the reason? Thank you!

  • I believe the problem is uninitialized values throw undefined behaviour. Your linux compiler throws in 0 while the windows one gives garbage value, anyways if this is the problem, both of the ways are not acceptable – emetsipe Nov 19 '22 at 15:37
  • `TreeNode *root;` is an uninitialized value on any platform. This is a bug, even when it appears to work correctly because you got lucky on the initial value. – Retired Ninja Nov 19 '22 at 15:38
  • Yep. This could have been the case; but then in case of linux it is giving correct values and not 0. – Soham Ratnaparkhi Nov 19 '22 at 15:39
  • [Always enable compiler warnings](https://stackoverflow.com/q/57842756/995714) and read them. [Your code has lots of uninitialized warnings and also undefined behaviors](https://godbolt.org/z/sf44TnxP7). Also [don't upload images of code/data/errors](https://meta.stackoverflow.com/q/285551/995714), just copy the output text and paste here in proper format – phuclv Nov 19 '22 at 15:40
  • @RetiredNinja Thank you. Got my answer. I just initialized it to NULL and everything started working as normal – Soham Ratnaparkhi Nov 19 '22 at 15:41
  • 1
    There is no reason except that Linux *happened* to give correct value. Failure is not guaranteed. Always deal with compiler warnings. MSVC says "uninitialized local variable 'root' used". – Weather Vane Nov 19 '22 at 15:41
  • Turn warnings on. The compiler will output: :64:13: warning: 'root' may be used uninitialized [-Wmaybe-uninitialized] 64 | int h = height(root); | ^~~~~~~~~~~~ :45:15: note: 'root' was declared here 45 | TreeNode *root; | ^~~~ – 0___________ Nov 19 '22 at 15:41
  • You're lucky in this case, but just change the compiler or compiler options and you can get a different result immediately. See my link above that produces an error on Linux? [(Why) is using an uninitialized variable undefined behavior?](https://stackoverflow.com/q/11962457/995714) – phuclv Nov 19 '22 at 15:43

0 Answers0