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

Answer 1

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

10 
 20 
  30 
   40 
    50 
     60 
      70 
       75 
        80

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