Yes,it works for binary search tree only
On Sat, Jan 29, 2011 at 2:22 PM, nphard nphard <nphard.nph...@gmail.com>wrote:
> 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<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.
