# Binary Search Trees C++

## Recommended Posts

Sabonis    169
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
Fruny    1658
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
Sabonis    169
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
Boder    938
Pass it in as a parameter and then increment it when you move to a child node.

##### Share on other sites
Fruny    1658
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 traversal

int 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
Sabonis    169

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
Fruny    1658
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
Sabonis    169
Ok thanks for all your help, saved me some money! :D