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 <ritugarg.c...@gmail.com> 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 <harishp...@gmail.com> 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 <ritugarg.c...@gmail.com> 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 <nphard.nph...@gmail.com> 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 <ritugarg.c...@gmail.com> 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 <nphard.nph...@gmail.com> 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++ <avpostni...@gmail.com>
> >> 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 algogeeks@googlegroups.com.
> >> > > > > To unsubscribe from this group, send email to
> >> > > > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2Bunsubscribe@googlegroups
> >> > > > > .com>
> >> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252Bunsubscribe@googleg
> >> roups.com>
>
> >> > > <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252Bunsubscribe@googleg
> >> > > roups.com>
> >> <algogeeks%252bunsubscr...@googlegroups.com<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 algogeeks@googlegroups.com.
> >> > > To unsubscribe from this group, send email to
> >> > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2Bunsubscribe@googlegroups
> >> > > .com>
> >> <algogeeks%2bunsubscr...@googlegroups.com<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 algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com<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 algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com<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 algogeeks@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.
