Public Group

# Binary Search Trees C++

This topic is 4457 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Does anyone know how to accurately get the height of a binary search tree? (where it is unbalanced and could have any amount of elements?)

##### Share on other sites
You can do it recursively. Traverse the binary tree, keeping track of the current level of recursion and the maximum level of recursion. The height of the tree will be that maximum at the end of the traversal (+/- 1 depending on how you count the recursion levels).

Let's see if you can write the function with that information -- show your work. [smile]

##### Share on other sites
ok so i have a depth first traversal...
mInOrder(NODE *Current_Node){        if(Current_Node ==0)	{		cout << "Current tree is empty" << endl;		return;	}	if(Current_Node->left_child!=0)		mInOrder(Current_Node->left_child);	if(Current_Node->right_child!=0)		mInOrder(Current_Node->right_child);		return;}

[edits just fixing code]
and I don't really see where I could put a counter to count the levels

##### Share on other sites
Pass it in as a parameter and then increment it when you move to a child node.

##### Share on other sites
Quote:
 Original post by BoderPass it in as a parameter and then increment it when you move to a child node.

And pass the total height as a reference parameter. You will need a second function that calls the recursive traversal one.

void height_impl(NODE* tree, int depth, int& maxdepth); // recursive traversalint height(NODE* tree){   int result = 0;   height_impl(tree, 0, result);   return result;}

(though actually it doesn't really matter - you're working with a tree, so you can't really do much tail recursion...)

##### Share on other sites
mInOrder(NODE *Current_Node){        if(Current_Node ==0)	{		cout << "Current tree is empty" << endl;		return;	}	if(Current_Node->left_child!=0)        {                CurrentLevel++;		mInOrder(Current_Node->left_child);                CurrentLevel--;         }	if(Current_Node->right_child!=0)        {                CurrentLevel++;		mInOrder(Current_Node->right_child);                CurrentLevel--;         }        if(CurrentLevel > MaxLevel)           MaxLevel=CurrentLevel;        CurrentLevel--;		return;}int tree::getheight(){   return MaxLevel;}

might this work too? and just take the height as the maximum level? (CurrentLevel and MaxLevel are class members) Its just pseudocode right now, fixing :)

##### Share on other sites
yeah, it should work, though it is simpler (in my eyes) to directly pass level+1 to the function call rather than keep an external level which you increment before and decrement after the function call.

void height_impl(NODE* tree, int depth, int& maxdepth){   if(depth>maxdepth) maxdepth=depth;   if(tree->left_child != 0)      height_impl(tree->left_child, depth+1, maxdepth);   if(tree->right_child != 0)      height_impl(tree->right_child, depth+1, maxdepth);}

##### Share on other sites
Ok thanks for all your help, saved me some money! :D

• 12
• 9
• 13
• 41
• 15