Here is one other way:
Planning to do a level order traversal using a Queue and a small marker
field whose storage in the queue is proportional to the height of the tree.
Here is a psuedo code for it..
// Returns the height of the binary tree as int.
int find_bintree_height(root) {
unsigned height = 0;
if (root) {
Queue::Push(root);
Queue::Push("#"); // where "#" is used as marker to indicate level..
}
bool is_leaf_avail = false; // a flag to indicate whether end of tree is
reached.
for (;!Queue::isEmpty();) {
ele = Queue::Pop();
if (ele == "#") {
if (is_leaf_avail)
Queue::Push("#") //push it till leaf is not reached..
is_leaf_avail = false; // reset it..
height++;
continue;
} // end of outer if
if (ele->left || ele->right)
is_leaf_avail = true;
if (ele->left) Queue::Push(ele->left);
if (ele->right) Queue::Push(ele->right);
}
return (height)
}
This is a hasty psuedo C++ code.. Seems to be fine from cursory look.. Let
me know
Thanks,
Balaji
On Thu, Jul 8, 2010 at 8:48 AM, jalaj jaiswal <jalaj.jaiswa...@gmail.com>wrote:
> @ above he asked iterative .
> .. use a stack to eliminate recursion ...
>
>
> On Thu, Jul 8, 2010 at 9:00 PM, Anand <anandut2...@gmail.com> wrote:
>
>> height(struct *node)
>> {
>> int left_height;
>> int right_height;
>> if(node == NULL)
>> return 0;
>> else
>> left_height = height(node->left);
>> right_height = height(node->right);
>> return (1+ max(left_height, right_height));
>>
>>
>> }
>>
>> On Thu, Jul 8, 2010 at 2:46 AM, sharad <sharad20073...@gmail.com> wrote:
>>
>>> write algo to find hieght of BINARY tree ITERATIVELY
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> With Regards,
> Jalaj Jaiswal
> +919026283397
> B.TECH IT
> IIIT ALLAHABAD
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
