I highlighted the code which I feel need a change. Do let me know if it
correct.
LinkNode *levelOrderTraversal(node *root, int level)
{
LinkNode *ptr1, *ptr2, temp;
if(root == NULL)
return NULL;
if(level == 1)
return createLinkNode(root);
else
{
ptr1 = levelOrderTraversal(root->left, level-1);
ptr2 = levelOrderTraversal(root->right, level-1);
if(ptr1 == NULL && ptr2 == NULL)
return NULL;
else if(ptr1 == NULL)
return ptr2;
else if(ptr2 == NULL)
return ptr1;
else
{
* temp = ptr1;
while(ptr1->next)
ptr1= ptr1->next;
ptr1->next = ptr2;
return temp;* (Will always return the head of the linked list to store
it in the array)
}
}
}
On Fri, Jul 30, 2010 at 8:18 AM, vineel yalamarth <
vineelyalamar...@gmail.com> wrote:
> Dude, yeah I got the algo, but can u write java code for that
>
>
> On Fri, Jul 30, 2010 at 6:03 PM, karthik ramanathan <
> nathankart...@gmail.com> wrote:
>
>> Do a BFS, by having a queue and keep inserting the nodes into it.
>> You should know how many nodes are there in each level, for which you can
>> have a variable to count the number of nodes in each level.
>> The when you remove from your queue do connect these nodes till your
>> count. You may need to use one more temp variable to not to lose the
>> previous level node count when you compute the next level node count.
>> Repeat the same for all the level.
>>
>> RK
>>
>>
>>
>> On Fri, Jul 30, 2010 at 11:21 AM, Amit Agarwal <lifea...@gmail.com>wrote:
>>
>>> A simple queue implementation will do.
>>>
>>> -Regards
>>> Amit Agarwal
>>> blog.amitagrwal.com
>>>
>>>
>>>
>>>
>>> On Fri, Jul 30, 2010 at 9:22 AM, Priyanka Chatterjee <
>>> dona.1...@gmail.com> wrote:
>>>
>>>>
>>>>
>>>> On 30 July 2010 02:59, Priyanka Chatterjee <dona.1...@gmail.com>wrote:
>>>>
>>>>> Algo: 1. find height of tree
>>>>> 2. do level order traversal
>>>>> i> at each level store the address of each tree node in the
>>>>> data part of a linked node and form linked list of the nodes
>>>>> ii> store the header of a linked list at a certain level
>>>>> in an array
>>>>> 3. return array.// gives final structure
>>>>>
>>>>>
>>>>> complexity - T(n) =O(n)
>>>>> S(n)=O(h+n ) //h=height of tree
>>>>>
>>>>> //CODE
>>>>>
>>>>> //tree structure
>>>>> struct node {
>>>>> int data;
>>>>> struct node * left, *right};
>>>>>
>>>>> // linked list structure
>>>>> struct linkNode{
>>>>> struct node * data;
>>>>> struct linkNode * next;
>>>>> }
>>>>>
>>>>> struct linkNode** func(struct node * root){
>>>>>
>>>>> struct linkNode ** array;
>>>>>
>>>>> int i, h=height(root);
>>>>> for(i=1;i<=h;i++)
>>>>> array[i-1]=levelOrderTraversal(root, i);
>>>>>
>>>>> return array;// final tree structure
>>>>> }
>>>>>
>>>>> //max height of tree
>>>>> int height(struct node *root){
>>>>> int hL=height(root->left);
>>>>> int hR=height(root->right);
>>>>> return 1+ HR>HL?HR:HL;
>>>>> }
>>>>>
>>>>>
>>>>>
>>>>> struct nodelink* levelOrderTraversal(struct node*root, int level){
>>>>> if(root==NULL) return NULL;
>>>>>
>>>>> if (level==1)
>>>>> return createLinkNode(root); // create a node of a singly l
>>>>>
>>>>>
>>>>> struct LinkNode *ptr;
>>>>> if(level>1){
>>>>> struct nodeLink * ptr1, *ptr2;
>>>>> ptr1=levelOrderTraversal(root->left,level-1);
>>>>> ptr2=levelOrderTraversal(root->right,level-1);
>>>>>
>>>>
>>>> if(ptr1==NULL && ptr2==NULL) return NULL;
>>>> if(ptr1==NULL) return ptr2;
>>>> if(ptr2==NULL) return ptr1;
>>>> ptr1->next=ptr2;
>>>>
>>>> return ptr2;
>>>>
>>>>> }
>>>>>
>>>>> }
>>>>>
>>>>>
>>>>
>>>>> struct linkNode * createLinkNode(struct node * root){
>>>>>
>>>>> struct linkNode* newNode=(struct linkNode*) malloc(sizeof(struct
>>>>> linkNode));
>>>>>
>>>>> newNode->data=root;
>>>>>
>>>>> newNode->next=NULL;
>>>>>
>>>>> }
>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> Thanks & Regards,
>>>>> Priyanka Chatterjee
>>>>> Final Year Undergraduate Student,
>>>>> Computer Science & Engineering,
>>>>> National Institute Of Technology,Durgapur
>>>>> India
>>>>> http://priyanka-nit.blogspot.com/
>>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> Thanks & Regards,
>>>> Priyanka Chatterjee
>>>> Final Year Undergraduate Student,
>>>> Computer Science & Engineering,
>>>> National Institute Of Technology,Durgapur
>>>> India
>>>> http://priyanka-nit.blogspot.com/
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To post to this group, send email to algoge...@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 algoge...@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 algoge...@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.
>>
>
>
>
> --
> Regards,
> vineel.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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 algoge...@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.
