Binary Tree Height

[tpham79]

hello, i have a question would like to ask if anyone can help me.

I'm implementing a binary tree. the problem that i need to find the height of the tree. if anyone have any idea, please help

ps: in any language, or just plain english is fine
greatly appreciated.

Tai

[Trung Quốc]

will help you wyen I get home later this afternoon. :)
BTW, how do you fill the tree? try to complete each row? or just smaller go to the right and bigger go to the left?

[tpham79]

smaller to the left and bigger to the right, it is just a normal tree, it is not balance, or full, i just inserted as i go along.

Tai

tahnks in advance

[Trung Quốc]

This is going to use a recursive so save all unsave work. Anh I don't know if this would work correctly. Don't have the code to generate the binary tree so I write this psuedo code for you.

Create a global integer name numberofdepthcount or whatever you wanted and initial it to 0

Create a function depthcout (pass in the mypointer as a pointer to the list)
if (leftptr == NULL and rightptr==NULL) then //have no child
output numberofdepthcount
exit function
end if
increment numberofdepthcount
set mypointer=mypointer.totheleft
now call the depthcout function and pass in the variable mypointer
decrementnumber of death count //why? because you are in the left hand side and have no where to go you have to go back to go to the right. :)
set mypointer=mypointer.totheright
now call the depthcout function and pass in the variable mypointer




I think that should do it. However check my logic :D

If it is not working, send me everything you have so far so that I can look at it to see where is the trouble.

Goodluck

QT

[CAptain DaLaZBoi]

damn......... nho lai.............nhuc cai ddau........

wacky...

[tpham79]

THanks Quoc Trung, I've thought about the method of go to every leaf and see how deep it is, and compare to the current height i have, but it doesn't seem to work, maybe i have to put a variable into each node and recursively check every node to see wheather that node is on the same level as the others.

anyway, thanks for all your input

[Trung Quốc]

try to use the pseudo code I have up there. It should work. However, if you want to use the computer to give you the heighest level then create another variable name currentdepth then replace
"if (leftptr == NULL and rightptr==NULL) then //have no child
output numberofdepthcount
exit function
"
by
if (leftptr == NULL and rightptr==NULL) then //have no child
if currentdepth < numberofdepthcount then
currentdepth = numberofdepthcount
end if
exit function

[tpham79]

THanks Quoc Trunh, you're very helpful, as you said, the first psuedo should work, i implement it, and it keep giving me off by 1.... took me awhile to find out the problem is, it just that i initialize the variable height in the insert function by 1.

anyway, glad that you could help.

thanks

Tai

[thanhuyen]

Check out this code segment. I wrote it in C
LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL

/*
* The depth of the binary tree spanning from curNode
*/
int depth(Node *curNode)
{
int leftLen = 0;
int rightLen = 0;

if (curNode->left == NULL && curNode->right == NULL)
return (int) 0;
else
{
if (curNode->left != NULL)
leftLen = depth(curNode->left);
if (curNode->right != NULL)
rightLen = depth(curNode->right);

if (rightLen > leftLen)
leftLen = rightLen;

return (int) 1+leftLen;
}
}


To invoke this recursive function on your tree, pass it the root:

printf("%s %d\n", "The depth of the binary tree is ", depth(root));


Good luck,
-ThanhUyen

[tpham79]

thanks, but i got it done couple of days ago, and here is my code in java. thanks all your inputs.

counter = 1; //if one node in the tree
height = 0; //if no node in the tree

public void height(Node node) {
if (node != null) {
if (node.getLeftChild() == null && node.getRightChild() == null)
height = (height < counter)? counter : height;
counter++;
height(node.getLeftChild());
height(node.getRightChild());
counter--;
}
}