sakshi
BAN USERSo, here is my code..
done dry testing only :-)
int roll(struct node *root)
{
if(root == NULL) return 0;
int l_sum=0, r-sum=0;
l_sum = roll(root->left);
r_sum = roll(root->right);
root.data = root.data + root->right.data + r_sum;
return (node->left.data + l_sum);
}
If we have performed the requisite algorithm (rollUp) on the right subtree of a node, and now we need to perform that on the current node, we can just consider the value of the right node.
But the issue here is that the right node had ignored it's left subtree for getting it's value(because at any node, all the nodes in the right subtree have value greater than it.)
But this neglected left subtree of the current node's right node is important for calculating the value of current node.
So what we can do is.. we can try to remember the left subtree's sum, at any node of the tree, while doing recursion.
Here is my solution (tested :) )
#include <stdio.h>
#include<conio.h>
#include<malloc.h>
#include<string.h>
struct node{
char *data;
struct node *next;
};
typedef struct node *NODE;
void strtok_my(char* input ,char* delims);
NODE head = NULL;
void insert(char*data, int len)
{
NODE ptr;
NODE nptr;
if(len)
{
if(head == NULL)
{
head = (NODE)malloc(sizeof(struct node));
head->data = (char*)(malloc(sizeof(char)*len + 1));
memset(head->data, NULL,len+1);
strncpy(head->data, data, len);
head->next = NULL;
return;
}
nptr = (NODE)malloc(sizeof(struct node));
nptr->data = (char*)(malloc(sizeof(char)*len + 1));
memset(nptr->data, NULL,len+1);
strncpy(nptr->data, data, len);
nptr->next = NULL;
for(ptr = head; ptr->next != NULL; ptr= ptr->next);
ptr->next = nptr;
}
return;
}
void print()
{
NODE ptr;
for(ptr = head; ptr; ptr= ptr->next)
{
printf(" %s ", ptr->data);
}
}
void main()
{
char *str = "heabcateabcaabcmango";
char *delims = "abc";
strtok_my(str, delims);
print();
getch();
}
void strtok_my(char* input ,char* delims)
{
char *p1; char *p2;
p1= input; p2 = input;
while(*p1 && *p2)
{
if(*(p2+1)== NULL || *(p2+2)== NULL)
{
while(*p2)p2++;
insert(p1,(p2-p1));
return;
}
if((*p2 == 'a') && (*(p2 + 1)== 'b')&& (*(p2+2)== 'c'))
{
insert(p1,(p2-p1));
p2 = p2 + 3;
p1=p2;
}
else
{
p2++;
}
}
}
- sakshi August 16, 2012