Height of Skewed Binary Search Tree

Question

I have implemented the code as follows, In this I have made two functions to calculate the height of binary search tree using recursion and without recursion.

#include <iostream>
#include <list>
using namespace std;

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

struct node *newNode(int item)
{
    struct node *temp = new node;
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

void inorder(struct node *root)
{
    if (root != NULL)
    {
        inorder(root->left);
        printf("%d ", root->key);
        inorder(root->right);
    }
}

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 if (key > node->key)
        node->right = insert(node->right, key);

    return node;
}

int heightRecursive(struct node *node)
{
    if (node == NULL)
        return -1;
    else
    {
        int lDepth = heightRecursive(node->left);
        int rDepth = heightRecursive(node->right);

        if (lDepth > rDepth)
            return (lDepth + 1);
        else
            return (rDepth + 1);
    }
}

int heightNonRecursive(node* root)
{
    if (root == NULL) {
        return 0;
    }
 
    list<node*> queue;
    queue.push_back(root);
 
    node* front = NULL;
    int height = 0;
 
    while (!queue.empty())
    {
        int size = queue.size();
 
        while (size--)
        {
            front = queue.front();
            queue.pop_front();
 
            if (front->left) {
                queue.push_back(front->left);
            }
 
            if (front->right) {
                queue.push_back(front->right);
            }
        }
 
        height++;
    }
 
    return height;
}
 

int main()
{
    struct node *root = NULL;
    root = insert(root, 10);
    insert(root, 20);
    insert(root, 30);
    insert(root, 40);
    insert(root, 50);
    insert(root, 60);
    insert(root, 70);
    insert(root, 75);
    insert(root, 80);

    inorder(root);
    int h = heightRecursive(root);
    cout << "\n\nHeight of tree using recursive function: " << heightRecursive(root);
    cout << "\nHeight of tree using non-recursive function: " << heightNonRecursive(root);

    return 0;
}

I have implemented a skewed binary tree like 10->20->30->40->50->60->70->75->80, but in the heightNonRecursive() function, I am getting the height of this binary search tree as 9. Please help where I am doing mistake.

Output of above code:

10 20 30 40 50 60 70 75 80 

Height of tree using recursive function: 8
Height of tree using non-recursive function: 9

[What is a debugger and how can it help diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — PaulMcKenzie, Nov 20 '21 at 13:09

Barmak Shemirani · Answer 1 · 2021-11-20T13:16:20.480

You have 9 different numbers in increasing order, in unbalanced tree, so the height should be 8, which is correct with recursive function.

With non-recursive function, you just have to start with height = -1;, it should return 0 if there is only one item in the tree.

int heightNonRecursive(node* root)
{
    if (root == NULL) 
        return 0;

    list<node*> queue;
    queue.push_back(root);
    node* front = NULL;
    int height = -1; //<-start at -1
    while (!queue.empty())
    {
        int size = queue.size();
        while (size--)
        {
            front = queue.front();
            queue.pop_front();
            if (front->left) 
                queue.push_back(front->left);
            if (front->right) 
                queue.push_back(front->right);
        }
        height++;
    }
    return height;
}

Height of Skewed Binary Search Tree

1 Answers1