tree height

[gotclout]

I was trying to help a friend out he wanted an algorithm to calculate tree height linearly

so I told him to do a kind of
left right search which is of course O(n^?) whatever, but using loops its doable right

so start at the root keep going left adding the the right child to a container until you get to no more left nodes
then go to the highest right node in the container and repeat until you have visted
the last left child of each node in the container
all while maintaining a max height and current height counter

then repeat the above switiching left and right

I know that would be really slow, but still linear

I kind of just thought it up off of the top of my head, wanted to make sure I didnt point him in the wrong direction, ideas thoughts comments welcome

[Alvaro]

[syntax="cpp"]unsigned tree_height(Node *s){
if(!s)
return 0;
return std::max(tree_height(s->left),tree_height(s->right))+1;
}
[/syntax]
There.

[Bugdude]

[syntax="cpp"]unsigned tree_height(Node *s){
if(!s)
return 0;
return std::max(tree_height(s->left),tree_height(s->right))+1;
}
[/syntax]
There.

I thought the OP wanted an iterative solution, not recursive.

[Alvaro]

I thought the OP wanted an iterative solution, not recursive.

Unclear, but you might be right.

If you are allowed to use a stack, you can remove the recursion, but this is not a truly iterative solution.

If your tree also has pointers to the parent node then it's doable. For instance, you can keep a pointer to the previously visited node, so you can always know whether you are visiting the current node from the parent (first visit), or you are coming back from the left subtree or your are coming back from the right subtree. If you are coming from the parent, go to the left; if from the left, go to the right; if from the right, go to the parent. Stop the loop when you come back to the root.

I'll write some code later if I have the time.

[gotclout]

yes it was supposed to be iterative,

and yes a container/stack is usable so then for the most part the pseudo algorithm above seems to be the right idea...thanks