Why I am getting different output for finding heigth of Binary Search Tree?

Question

I have written two different programs for finding height of Binary Search Tree but both of them are giving different output as my logic of calculating the height is same in both functions:

int findheight(Node* node) {
    if (node == NULL)
        return 0;
    int lh = 0, rh = 0;
    if (node->left != NULL)
        lh = findheight(node->left);
    if (node->right != NULL)
        rh = findheight(node->right);
    return max(lh, rh) + 1;
}

2nd Function to calculate heigth of binary search tree:

int findheight(struct node* node) {
    if (node == NULL)
        return 0;
    else {
        int ldepth = findheight(node->left);
        int rdepth = findheight(node->right);

        if (ldepth > rdepth)
            return (ldepth + 1);
        else
            return (rdepth + 1);
    }
}

For this test case 100 11 11 17 30 40 71 90 92 117 148 151 157 160 174 193 203 227 263 276 280 291 296 307 311 322 340 345 346 373 374 398 402 411 419 437 441 446 450 476 476 493 503 513 523 530 533 545 573 573 593 597 599 603 628 642 650 651 655 658 679 704 711 715 737 745 746 783 783 797 802 808 823 825 826 827 832 834 845 857 861 871 872 877 883 894 907 921 922 940 943 949 951 952 956 958 959 976 979 987 997 2nd function gives output 100 while 1st function gives 96

For this test case: 100 7 10 29 32 40 52 55 76 83 103 116 122 123 135 162 163 170 184 192 193 205 221 226 235 253 257 259 298 305 310 338 349 388 396 397 399 408 412 419 429 443 443 461 481 485 490 504 508 509 515 517 522 545 547 564 580 596 601 611 616 622 635 664 665 676 684 687 688 689 695 703 724 734 764 771 775 815 816 819 827 849 852 855 864 882 887 893 902 911 937 940 941 943 965 966 968 984 985 993 998 2nd function gives output:100 and 1st function gives 99

Entire code for finding height of Binary Search Tree:

    #include <bits/stdc++.h>
    using namespace std;

    struct node{
    int key;
    struct node *left;
    struct node *right;
    };

    struct node *newnode(int item){
    struct node *temp = (struct node*)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
    }

    struct node *insert(struct node *node,int key){
        if(node==NULL) return newnode(key);

        if(key< node->key)
            node->left = insert(node->left,key);
        else
            node->right = insert(node->right,key);

        return node;
    }

   /*Insert any one of the functions mentioned above*/

    int main(){
        int n,m;
        cin>>n;
        struct node *root = NULL;
        for(int i=0;i<n;i++){
            cin>>m;
            root=insert(root,m);
        }
        cout<< maxdepth(root);

    return 0;
    }

Please edit your question instead of giving useful additional information in a comment. — Yunnosch, Jun 24 '17 at 07:04
Make sure that the tree looks like a tree. Even if the code for inserting values were available, I wouldn't study it to find out how the tree looks. You **do** use the same code for making the tree in both cases, don't you? — Yunnosch, Jun 24 '17 at 07:05
Apropos same, why is it `Node* node` != `struct node* node`? — Yunnosch, Jun 24 '17 at 07:06
https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ — Yunnosch, Jun 24 '17 at 07:08
https://stackoverflow.com/questions/2069367/how-to-debug-using-gdb — Yunnosch, Jun 24 '17 at 07:09
@4386427 This is my insert function `struct node *insert(struct node *node,int key){ if(node==NULL) return newnode(key); if(key< node->key) node->left = insert(node->left,key); else node->right = insert(node->right,key); return node; }` — rock stone, Jun 24 '17 at 07:10
Find smaller test cases. Create them systematically. Make sure you know the correct answer in advance. — molbdnilo, Jun 24 '17 at 07:16
As @Stargateur hinted: It would be easier all around, if you would delete the comments which you edited into your question. — Yunnosch, Jun 24 '17 at 07:18
@Yunnosch Done deleting the comments but this question is very difficult to debug as both functions give different output at specific test case only otherwise both give correct answer. — rock stone, Jun 24 '17 at 07:21
@molbdnilo This question is very difficult to debug as both functions give different output at specific test case only, otherwise both give correct answer. — rock stone, Jun 24 '17 at 07:22
Please edit the question to show the useful additional information on the input function inside the question, instead of hiding it in a comment.... — Yunnosch, Jun 24 '17 at 07:22
I find the question interesting but second the case to find smaller test cases that show similar problem. — MrJalapeno, Jun 24 '17 at 07:22
@rockstone - Do you run both functions on the same tree? Is everything in your program the same except that you change this function? — Support Ukraine, Jun 24 '17 at 07:22
While editing anyway, please make a [mcve]. I.e. give us a code foundation on which we can apply both your functions to what is guaranteed to be the same tree. Preferrably a smaller tree. Use two different function names to have both functions avaialble in one code file. Run both of them on the same tree and show both outputs. Align the prototypes to avoid any suspicion of an error being caused in the difference. Do not forget to show the definition of the node type. — Yunnosch, Jun 24 '17 at 07:24
Weird inclusion. I doubt that I can compile that code with my C compiler (I prefer gcc). — Yunnosch, Jun 24 '17 at 07:34
Both functions returns 100 on both test cases - see http://ideone.com/6SsQo9 — Support Ukraine, Jun 24 '17 at 07:36
@rock yes...... you can try yourself - just press the "fork" link just above the code. Then you can change input as you like and run it — Support Ukraine, Jun 24 '17 at 07:39

score 1 · Accepted Answer · answered Jun 24 '17 at 07:50

The functions both return the same value. You have something else in your code that generates the difference in output.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct node{
    int key;
    struct node *left;
    struct node *right;
};
int findheight(struct node* node) {
    if (node == NULL)
        return 0;
    else {
        int ldepth = findheight(node->left);
        int rdepth = findheight(node->right);

        if (ldepth > rdepth)
            return (ldepth + 1);
        else
            return (rdepth + 1);
    }
}
int findheight2(struct node* node) {
    if (node == NULL)
        return 0;
    int lh = 0, rh = 0;
    if (node->left != NULL)
        lh = findheight(node->left);
    if (node->right != NULL)
        rh = findheight(node->right);
    return (lh>rh ?lh : rh) + 1;
}
struct node *newnode(int item){
    struct node *temp = (struct node*)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

struct node *insert(struct node *node,int key){
    if(node==NULL) return newnode(key);

    if(key< node->key)
        node->left = insert(node->left,key);
    else
        node->right = insert(node->right,key);

    return node;
}

/*Insert any one of the functions mentioned above*/

int main(){
    int n,m;
    n=100;
    struct node *root = NULL;
    for(int i=0;i<n;i++){
        m = n;
        root=insert(root,m);
    }
    printf("%d", findheight(root));
    printf("%d", findheight2(root));
    return 0;
}

Why I am getting different output for finding heigth of Binary Search Tree?

1 Answers1