Unable to find height of BST

Question

Using recursion I am trying to find height of tree but the output seems wrong. Any errors?

#include <iostream>

struct node{
    int data;
    node* left, *right;
};

node* getNode(int item){
    node* new_node = new node;
    new_node->data = item;
    new_node->left = new_node->right = nullptr;
    return new_node;
}

node* insert(node* root, int item){
    if(root == nullptr){
        root = getNode(item);
    }
    else if(item < root->data){
        root->left = insert(root->left, item);
    }
    else if(item > root->data){
        root->right = insert(root->right, item);
    }
    return root;
}

int height(node* root){
    if(root == nullptr){
        return 0;
    }
    else{
        return 1+std::max(height(root->left), height(root->right));
    }
}

int main()
{
    node* root;
    root = insert(root, 40);
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 80);
    root = insert(root, 30);
    root = insert(root, 1);
    std::cout << "\nheight of Tree: " << height(root);

    return 0;
}

Tree should have height 3 (if i am not wrong) but its showing 4.
I am using GNU GCC compiler with Code::Blocks IDE it works there,
But when I am running same code on Programiz c++ online compiler it shows Segmentation fault so maybe the I am doing something wrong.
Regards

*Tree should have height 3 (if i am not wrong) but its showing 4.* -- When you debugged the code, what did you observe? — PaulMcKenzie, Nov 06 '20 at 05:43

score 5 · Accepted Answer · answered Nov 06 '20 at 05:49

5

Right away, this code:

int main()
{
    node* root;  // <-- uninitialized
    root = insert(root, 40); // <-- Using an uninitialized pointer
    //...
}

is faulty.

The root is an uninitialized pointer, and passing that uninitialized pointer to insert will invoke undefined behavior.

The probable fix is to simply do:

node* root = nullptr;

answered Nov 06 '20 at 05:49

PaulMcKenzie

34,698
4
24
45

The variable is uninitialized, meaning it could have any value, even one that makes your code "work". Please [read this](https://stackoverflow.com/questions/367633/what-are-all-the-common-undefined-behaviours-that-a-c-programmer-should-know-a). As a matter of fact, a good compiler should have warned you that the variable is not initialized. – PaulMcKenzie Nov 06 '20 at 12:10

score 2 · Answer 2 · answered Nov 06 '20 at 05:53

Your code is returning 4 because you’re counting the number of nodes on the longest path down from the root, rather than the number of edges. Notice, for example, that you’re considering a one-node tree to have height 1, whereas it’s conventionally considered to have height 0.

There’s an easy fix to this, and that’s to change your base case. As weird as it seems, the convention is to treat an empty tree as having height -1. Change your base case appropriately and watch what happens. Can you account for why this works?

(Also, as pointed out by the other answer, your code works with an uninitialized pointer, which can literally destroy the fabric of spacetime and teleport us all to a Dimension of Infinite Peril. Initializing that pointer to nullptr should fix that. Pro tip: run your code under valgrind to see these sorts of errors in real-time!)

Unable to find height of BST

2 Answers2