@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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
