help wiht finding height of tree

[panchaga]

hi,

i have been working on binary search trees. i am finding it difficult to find the height of the tree. i am particualry confused with how to find the left height an right height seperateley.

all of the algorithms give psuedocode as comparing left height and right height and return which ever is grater. but how to find the heigts of left subtree and right subtree is my question.

thank you

 

[Casiopea]

I guess you are working with recursive functions. In that case, you should use a base case: (when the tree is null and return 0), otherwise it returns the maximum between left and right + 1.
int size(){
if (mtree==null)
return 0
else
return maximum((this->left)->size(),(this->right)->size())+1;
}
don't forget to create a maximun function which returns the maximum between two numbers.

 

[ArkM]

struct Node
{
  Node* pleft;
  Node* pright;
  int height() const;
};

int Node::height()
{
  int lh = 0, rh = 0;
  if (pleft)
     lh = pleft->height();
  if (pright)
     rh = pright->height();
  return (lh>rh?lh:rh) + 1;
}

struct Tree
{
  Node* phead;
  int height() const { return phead?phead->height():0; }
};

Adjust this algorithm to your tree/node declarations...