Looks good. I concede that it works for a Binary "Search" Tree.
On Sat, Jan 29, 2011 at 1:35 AM, Ritu Garg <ritugarg.c...@gmail.com> wrote:
> @nphard,see the following approach carefully to know *if right pointer is
> pointing to right child or in order successor*
> *
> *Q = node->right
> IF (Q is not NULL)
> {
> /*Determine if Q is node's right child or successor*/
> /*Q is inorder successor of node*/
> IF (Q->left == node OR Q->left->val < node->val)
> {
> }
> /*Q is the right child of node*/
> ELSE IF (Q->left == NULL or Q->left->val > node->right)
> {
> }
> }
>
> 1. Q->left is smaller than or equal to node if Q is Inorder Successor of
> node
> 2. Q->left is either NULL or Q->left is greater than node if Q is right
> child of node
> *
> *Hence* in order traversal of right threaded BST without flag* is possible
>
>
>
>
>
> On Fri, Jan 28, 2011 at 9:40 AM, nphard nphard <nphard.nph...@gmail.com>wrote:
>
>> Not correct. You cannot assume that the right node always points to the
>> successor. If you do that, your traversal will be affected. Consider that
>> when you reach a node B from the right pointer of its parent A, you traverse
>> that subtree rooted at B in normal inorder. However, when you reach B from
>> its inorder predecessor C, you should have the knowledge that you have
>> visited that node's left subtree and should not visit again (which is only
>> known if you have the information that you are reaching that node through a
>> thread).
>>
>> On Thu, Jan 27, 2011 at 10:57 PM, Ritu Garg <ritugarg.c...@gmail.com>wrote:
>>
>>> @nphard
>>>
>>> ideally,a flag is required in right threaded tree to distinguish whether
>>> right child is a pointer to inorder successor or to right child.Even we can
>>> do without flag assuming that there ll be no further insertions taking
>>> place in tree and no other traversal is required.
>>>
>>> here we suppose that right pointer always gives the successor......
>>>
>>> The solution to get the linear inorder traversal is just tailored for a
>>> situation where there is no extra space,not even for stack!!!
>>>
>>> On Fri, Jan 28, 2011 at 5:42 AM, nphard nphard
>>> <nphard.nph...@gmail.com>wrote:
>>>
>>>> @Ritu - Do you realize that you cannot just convert a given binary tree
>>>> into right-threaded binary tree? You need at least 1 bit information at
>>>> each
>>>> node to specify whether the right pointer of that node is a regular pointer
>>>> or pointer to the inorder successor. This is because traversal is done
>>>> differently when you arrive at a node through its inorder predecessor.
>>>>
>>>> On Thu, Jan 27, 2011 at 7:22 AM, Ritu Garg
>>>> <ritugarg.c...@gmail.com>wrote:
>>>>
>>>>> solution is not too hard to understand!!
>>>>> 1. [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 !!
>>>>>
>>>>> last node in left sub tree of any node always have right pointer as
>>>>> NULL because this is the last node
>>>>>
>>>>> 2. 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.
>>>>> i said that it ll take O(n) time for well balanced tree.
>>>>> for a node at height h ,it takes O(h) to fill this node as successor of
>>>>> some other node.if combined for all sum(O(h)) h=1 to lg n ..total time ll
>>>>> come as O(n)
>>>>>
>>>>> 3. 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 ??
>>>>>
>>>>> when you ll process node 1,it ll be filled in as right child of 1.5
>>>>> there is no successor for 4.
>>>>>
>>>>> In Brief
>>>>>
>>>>> 1. Convert the tree to right threaded binary tree.means all right
>>>>> children point to their successors.
>>>>> it ll take no additional space.ll take O(n) time if tree is well
>>>>> balanced
>>>>>
>>>>> 2. Do inorder traversal to find ith element without using extra space
>>>>> because succssor of each node is pointed by right child.
>>>>>
>>>>> i hope you got it now!!
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> On Wed, Jan 26, 2011 at 5:31 PM, sankalp srivastava <
>>>>> richi.sankalp1...@gmail.com> 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 <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%2bunsubscr...@googlegroups.com>
>>>>>> <algogeeks%2Bunsubscribe@googlegroups .com>
>>>>>> > >> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
>>>>>> <algogeeks%252Bunsubscribe@googleg roups.com>
>>>>>> >
>>>>>> > >> > > <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
>>>>>> <algogeeks%252Bunsubscribe@googleg roups.com>
>>>>>> > >> <algogeeks%252bunsubscr...@googlegroups.com<algogeeks%25252bunsubscr...@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%2bunsubscr...@googlegroups.com>
>>>>>> <algogeeks%2Bunsubscribe@googlegroups .com>
>>>>>> > >> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@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%2bunsubscr...@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%2bunsubscr...@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%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 algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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 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.
