CODEWITHSUNDEEP
c++recursionheightbinary-search-tree
Dalkurac
Dalkurac

Reputation: 13

Total height of a binary search tree

I am working on building a Binary Search Tree and I want to create a function that records the height of each node and sums it. I am trying to use recursion.

For me, the difficulty lies in assigning a height to each node, and then going back and summing it up. Unless I can assign and record the height in one pass? Thanks in advance.

edit: Final code to show what worked for me for anyone who will look at this in the future. Thanks for the help guys.

BST.h

    int totalheight(node);
    int getHeight(node);

    class BST {
    Node root;
    public:
       BST { root = NULL; }
       int totalheight()
       { return ::totalheight(root);
    };


BST.cpp

int totalHeight(BSTNode* node)
{
   if (node == NULL)
      return -1;

   int leftHeight = getheight(node->left);
   int rightHeight = getheight(node->right);
   int totalheight = 1 + leftHeight + rightHeight; // +1 to count the root

   return totalheight;
} 

int getheight(BSTNode* node)
{
   if (node == NULL)
      return 0;

      return 1 + max(getheight(node->left), getheight(node->right)); 
}

main.cpp

    int main() {
       BST tree; // and various inserts

       tree.totalheight();
    } // main

Upvotes: 1

Views: 4321

Answers (1)

pippin1289
pippin1289

Reputation: 4939

One issue is here:

int myheight = max(leftheight, rightheight);

It should be:

int myheight = max(leftheight, rightheight) + 1;

You need the one to accound for this nodes height. Also in the code shown to recurse findHeight should be getHeight.

Here is an overall function:


int getheight(BSTNode* node)
{
    if (node == null)
        return 0;
    else
        return 1 + max(getHeight(node->left), getHeight(node->right)); 
} // getheight

Upvotes: 2

Related Questions