CODEWITHSUNDEEP
c++segmentation-faultbinary-search-tree
DK_bhai
DK_bhai

Reputation: 359

Unable to find height of BST

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;
}

enter image description here

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

Upvotes: 1

Views: 62

Answers (2)

templatetypedef
templatetypedef

Reputation: 372714

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!)

Upvotes: 2

PaulMcKenzie
PaulMcKenzie

Reputation: 35440

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;

Upvotes: 5

Related Questions