Trying to find the height in a BST

[aaronmk2]

I an trying to find the height in a binary search tree. I figured out how to count the leaves going directly left and directly right, but cannot figure out how to get he leaves in the middle.

int BST::height(){
	int tall =0;
	int tall1=0;
	BinNodePtr ptr=myRoot;
	if (ptr->left =='\0' && ptr->right =='\0') 
		return tall;//up to this part I know is correct.
	else {
		while (ptr->left) {
			ptr=ptr->left;
			tall++;
		}
		ptr=myRoot;
		while (ptr->right) {
			ptr=ptr->right;
			tall1++;
		}
	}
	if (tall>tall1)
	return tall;
	else 
		return tall1;

[daviddoria]

I think descriptive variable names and comments would be helpful here (and everywhere... :) )

I'm assuming 'tall' is the height? If so, name it 'height' and change the name of the function to GetHeight() or something like that. What is 'tall1'?

Add a comment to at least every conditional and every loop and I bet it will be come clear to you what is going on/wrong.

David

[mrnutty]

For Binary search trees or any data structures that are recursive in nature,
you will want to implement a recursive algorithm to solve most of its problems.Its not only easier to write, but its easier to understand as well. So with that said, consider this recursive algorithm that finds the height of a tree.

int BinaryTree:height(){
 return _height(this.root);
}
int BinaryTree::_height(const Node* root){
  if( isNull( root) ) return 0;
  int leftTreeMax = _height(root.getLeft()) + 1; //add one and move down
  int rightTreeMax = _height(root.getRight()) + 1; //add one and move down
  return std::max(leftTreeMax, rightTreeMax) + 1; //account for the root
}