Do inorder traversal, to find out the total no. of nodes.
Next time, do the inorder traversal but keeping the count of nodes visited
and stop when you visit n/2 nodes.
Non recursive In-order Traversal -
*inorder*(node)
*while* hasleftchild(node) *do*
node = node.left
*do*
visit(node)
*if* (hasrightchild(node)) *then*
node = node.right
*while* hasleftchild(node) *do*
node = node.left
*else*
*while* node.parent ≠ *null* *and* node == node.parent.right *do*
node = node.parent
node = node.parent
*while* node ≠ *null*
Source: Wikipedia
On Tue, Sep 27, 2011 at 9:13 PM, Sanjay Rajpal <[email protected]> wrote:
> Recursion also requires space, so the problem is how to traverse without
> extra space.
>
> Once this is done, nothing is left in the problem.
> Sanju
> :)
>
>
>
> On Tue, Sep 27, 2011 at 8:35 AM, Dheeraj Sharma <
> [email protected]> wrote:
>
>> @anshu
>> can middle element can be found if the no. of nodes are not given...
>>
>>
>> On Tue, Sep 27, 2011 at 8:34 PM, vikas <[email protected]>wrote:
>>
>>> a simple one is rabit-tortoise method, and using stackless traversal,
>>> facing a lot of corner cases in coding this, can someone check this as
>>> well?
>>>
>>> On Sep 27, 6:41 pm, anshu mishra <[email protected]> wrote:
>>> > its not o(n) it is O(max height of tree) :P
>>> > i have not seen the constraint.
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected].
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>>
>>
>> --
>> *Dheeraj Sharma*
>>
>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
Nitin Garg
"Personality can open doors, but only Character can keep them open"
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
