Well the solution is pretty simple.
What you have to do is just do inoder traversal of tree in reverse
order.
Here goes my C++ code for that
int ith_order(Tree *root,int i)
{
static int c;
static int ans;
if(root)
{
ith_order(root->right,i);
++c;
if(c==i)
return ans=root->data;
ith_order(root->left,i);
}
return ans;
}
please correct me if i am wrong :)
On Jan 26, 5:01 pm, sankalp srivastava <[email protected]>
wrote:
> I don't seem to understand ur solution .
> [quote] For every none leaf node , go to the last node in it's left
> subtree and mark the right child of that node as x [\quote]. How are
> we going to refer to the right child now ??We have removed it's
> reference now !!
>
> It is to be repeated for every node except the non leaf nodes . This
> will take O(n*n) time in worst case , say a leftist tree with only
> left pointers . root makes n-1 traversals , root's left subtree's root
> makes n-2 , and so on.
>
> Go to the largest node in the left subtree .This means go to the left
> subtree and keep on going to the right until it becomes null , in
> which case , you make y->right as x . This means effectively , that y
> is the predecessor of x , in the tree . Considering a very good code ,
> it may take O(1) space , but you will still need additional pointers.
> Take the case below .
>
> 1
> 2 3
> 1 1.5 2.5 4
>
> for node 2 , you will go to 1 , which is the successor of 2 , you make
> 2->right=1 .... but what about node 1.5 ???
> same is the case with node 3 ... 3->right=2.5 . How will we refer to 4
> now ??
>
> Now using inorder traversal with a count , I will start at 1->left , 2->left
> = 1 , then 2 ... then 2->right = 1 again . then 1 , and then 1-
> >right=3 ...clearly , this will not give us a solution .
>
> A reverse inorder looks just fine to me .
>
> On Jan 26, 3:14 pm, Ritu Garg <[email protected]> wrote:
>
>
>
>
>
>
>
> > @Algoose
>
> > I said ..*.For every node x,go to the last node in its left subtree and mark
> > the right child of that node as x.*
>
> > it is to be repeated for all nodes except leaf nodes.
> > to apply this approach ,you need to go down the tree.No parent pointers
> > required.
> > for every node say x whose left sub tree is not null ,go to the largest node
> > in left sub-tree say y.
> > Set y->right = x
> > y is the last node to be processed in left sub-tree of x hence x is
> > successor of y.
>
> > On Wed, Jan 26, 2011 at 3:27 PM, Algoose chase <[email protected]> wrote:
> > > @ritu
> > > how would you find a successor without extra space if you dont have a
> > > parent pointer ?
> > > for Instance from the right most node of left subtree to the parent of
> > > left
> > > subtree(root) ?
> > > @Juver++
> > > Internal stack does count as extra space !!
>
> > > On Wed, Jan 26, 2011 at 3:02 PM, ritu <[email protected]> wrote:
>
> > >> No,no extra space is needed.
> > >> Right children which are NULL pointers are replaced with pointer to
> > >> successor.
>
> > >> On Jan 26, 1:18 pm, nphard nphard <[email protected]> wrote:
> > >> > If you convert the given binary tree into right threaded binary tree,
> > >> won't
> > >> > you be using extra space while doing so? Either the given tree should
> > >> > already be right-threaded (or with parent pointers at each node) or
> > >> internal
> > >> > stack should be allowed for recursion but no extra space usage apart
> > >> from
> > >> > that.
>
> > >> > On Wed, Jan 26, 2011 at 3:04 AM, ritu <[email protected]> wrote:
> > >> > > it can be done in O(n) time using right threaded binary tree.
> > >> > > 1.Convert the tree to right threaded tree.
> > >> > > right threaded tree means every node points to its successor in
> > >> > > tree.if right child is not NULL,then it already contains a pointer to
> > >> > > its successor Else it needs to filled up as following
> > >> > > a. For every node x,go to the last node in its left subtree and
> > >> > > mark the right child of that node as x.
> > >> > > It Can be done in O(n) time if tree is a balanced tree.
>
> > >> > > 2. Now,Traverse the tree with Inorder Traversal without using
> > >> > > additional space(as successor of any node is available O(1) time) and
> > >> > > keep track of 5th largest element.
>
> > >> > > Regards,
> > >> > > Ritu
>
> > >> > > On Jan 26, 8:38 am, nphard nphard <[email protected]> wrote:
> > >> > > > Theoretically, the internal stack used by recursive functions must
> > >> be
> > >> > > > considered for space complexity.
>
> > >> > > > On Mon, Jan 24, 2011 at 5:40 AM, juver++ <[email protected]>
> > >> wrote:
> > >> > > > > internal stack != extra space
>
> > >> > > > > --
> > >> > > > > 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]<algogeeks%2Bunsubscribe@googlegroups
> > >> > > > > .com>
> > >> <algogeeks%[email protected]<algogeeks%252Bunsubscribe@googleg
> > >> roups.com>
>
> > >> > > <algogeeks%[email protected]<algogeeks%252Bunsubscribe@googleg
> > >> > > roups.com>
> > >> <algogeeks%[email protected]<algogeeks%25252Bunsubscribe@goo
> > >> glegroups.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 [email protected].
> > >> > > To unsubscribe from this group, send email to
> > >> > > [email protected]<algogeeks%2Bunsubscribe@googlegroups
> > >> > > .com>
> > >> <algogeeks%[email protected]<algogeeks%252Bunsubscribe@googleg
> > >> roups.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 [email protected].
> > >> To unsubscribe from this group, send email to
> > >> [email protected]<algogeeks%2Bunsubscribe@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 [email protected].
> > > To unsubscribe from this group, send email to
> > > [email protected]<algogeeks%2Bunsubscribe@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 [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.
