Sign in to follow this  
Sabonis

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Fruny    1658
Quote:
Original post by Boder
Pass 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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this