122 - Trees on the level

Moderator: Board moderators

rhtiwari
New poster
Posts: 5
Joined: Thu Jul 11, 2002 10:59 am

122 - Trees on the level

Hi,
I submitted the following program for Problem 122. However I get WA. The program works for the sample input as well as other inputs I devised.
------------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
char* value ;
struct node* left ;
struct node* right ;
} node ;

void buildtree() ;
void insertnode (char* valuestr, char* path) ;
void levelorder() ;
int complete() ;
void printlevelorder() ;

node* node_queue[256] ;
node* ptr_root = NULL ;
int morethanonce = 0 ;

int main()
{
/*build tree*/

/*First things first. Any non empty tree will require a root */
ptr_root = (node *)malloc(sizeof(node)) ;
ptr_root->value = NULL ;
ptr_root->left = NULL ;
ptr_root->right = NULL ;

buildtree() ;
/*put the nodes in node_queue in level order */
levelorder() ;
/*check to see if all the nodes are present */
if (morethanonce || !complete())
printf("not complete") ;
else
printlevelorder() ;
/*print the level order traversal of the tree */

return 0;
}

void buildtree()
{
char path[256] ;
char numstr[16] ; /*should be more than sufficient for a normal integer */
int tempchar ;
int nextpos ;

while (1)
{
tempchar = getchar() ;
while (tempchar != '(')
tempchar = getchar() ;
/* OK. We have the opening parentheses. Now see what follows it */

tempchar = getchar() ;
if (tempchar == ')')
break ; /*last entry was read */

/*OK. It was not ')'. So now it should be a digit, followed immediately by a , */
nextpos = 0 ;
while (tempchar != ',')
{
numstr[nextpos] = (char)tempchar ;
nextpos++ ;
tempchar = getchar() ;
}
/*OK. , read. Now terminate the numstr and see what follows the comma */
numstr[nextpos] = '\0' ;
tempchar = getchar() ;
if (tempchar == ')') /* No path string after the ,. This means the root node */
{
insertnode(numstr,"") ;
continue ;
}

/*OK. tempchar is either 'L' or 'R' followed by ')' */
nextpos = 0 ;
while (tempchar != ')')
{
path[nextpos] = (char)tempchar ;
nextpos++ ;
tempchar = getchar() ;
}
path[nextpos] = '\0' ;
/*Now we have the value for the node and the path. Insert the node in the tree */
insertnode(numstr, path) ;
}
}

void insertnode(char* valuestr, char* path)
{
int pos = 0 ; /*This variable will be used to track the path */
node* lastnode = NULL ;
node *tmp = NULL ;

/* Traverse the tree as per the path, building and inserting missing
intermediate nodes till the specified node is inserted. */
lastnode = ptr_root ;
while(path[pos] != '\0')
{
if (path[pos] == 'L')
{
if (lastnode->left == NULL) /*The intermediate node does not exist. Insert it*/
{
tmp = (node *)malloc(sizeof(node)) ;
tmp->value = NULL ;
tmp->left = NULL ;
tmp->right = NULL ;

lastnode->left = tmp ;
}
lastnode = lastnode->left ;
}
else if (path[pos] == 'R')
{
if (lastnode->right == NULL)
{
tmp = (node *)malloc(sizeof(node)) ;
tmp->value = NULL ;
tmp->left = NULL ;
tmp->right = NULL ;

lastnode->right = tmp ;
}
lastnode = lastnode->right ;
}
pos++ ;
}
/*The specified node along with all the intermediate nodes have been inserted.
lastnode points to the specified node */
if (lastnode->value != NULL)
{
lastnode->value = (char*)malloc(strlen(valuestr) + 1) ;
strcpy(lastnode->value, valuestr) ;
}
else
morethanonce = 1;
}

void levelorder()
{
int i = 0 ;
int nextpos = 0 ;

/*initialize node_queue to NULLs */
for (i = 0 ; i < 256 ; i++)
node_queue = (node *)NULL ;
/* first put a pointer to the root in the queue */
node_queue[nextpos] = ptr_root ;
nextpos++ ;

i = 0 ;
while (i < 256 && node_queue != NULL)
{
/*Add the children of node_queue at the end of the queue */
if (node_queue->left != NULL)
{
node_queue[nextpos] = node_queue->left ;
nextpos++ ;
}
if (node_queue->right != NULL)
{
node_queue[nextpos] = node_queue->right ;
nextpos++ ;
}
i++ ;
}
}

int complete()
{
int i = 0;

while (i < 256 && node_queue != NULL)
{
if (node_queue->value == NULL)
return 0 ; /*Incomplete tree */
i++ ;
}
return 1 ; /*Complete tree */
}

void printlevelorder()
{
int i = 0;
printf("%s",node_queue->value) ;

i++ ;
while (i < 256 && node_queue[i] != NULL)
{
printf(" %s", node_queue[i]->value) ;
i++ ;
}
}
------------------------------------------------------------------------------
Thanks and Regards,
Ratnakar

rhtiwari
New poster
Posts: 5
Joined: Thu Jul 11, 2002 10:59 am

Rune Zedeler wrote:Over here the program does not work, and I cannot understand how you have tested it with success.
In your main routine you have no loops at all. How should the program be able to test more than one three - and hence correctly run the test example which have two trees?
I assumed that the program would be tested one tree at a time. I will resubmit after putting in a loop.

rhtiwari
New poster
Posts: 5
Joined: Thu Jul 11, 2002 10:59 am
I tried putting in a lop, so that it reads all the input. It now works with the test input. However, now I get Time Limit exceeded. If I take out the loop and process each tree at a time, I get WA.

The code with the loop is given below:
--------------------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
char* value ;
struct node* left ;
struct node* right ;
} node ;

void buildtree() ;
void insertnode (char* valuestr, char* path) ;
void levelorder() ;
int complete() ;
void printlevelorder() ;

node* node_queue[256] ;
node* ptr_root = NULL ;
int morethanonce = 0 ;

int main()
{
/*build tree*/

/*First things first. Any non empty tree will require a root */

while (1)
{
morethanonce = 0 ;
ptr_root = NULL ;

ptr_root = (node *)malloc(sizeof(node)) ;
ptr_root->value = NULL ;
ptr_root->left = NULL ;
ptr_root->right = NULL ;

buildtree() ;
/*put the nodes in node_queue in level order */
levelorder() ;
/*check to see if all the nodes are present */
if (morethanonce || !complete())
printf("not complete\n") ;
else
printlevelorder() ;
/*print the level order traversal of the tree */
}
return 0;
}

void buildtree()
{
char path[256] ;
char numstr[16] ; /*should be more than sufficient for a normal integer */
int tempchar ;
int nextpos ;

while (1)
{
if ((tempchar = getchar()) == EOF)
exit(0) ;
while (tempchar != '(')
tempchar = getchar() ;
/* OK. We have the opening parentheses. Now see what follows it */

tempchar = getchar() ;
if (tempchar == ')')
return ; /*last entry was read */

/*OK. It was not ')'. So now it should be a digit, followed immediately by a , */
nextpos = 0 ;
while (tempchar != ',')
{
numstr[nextpos] = (char)tempchar ;
nextpos++ ;
tempchar = getchar() ;
}
/*OK. , read. Now terminate the numstr and see what follows the comma */
numstr[nextpos] = '\0' ;
tempchar = getchar() ;
if (tempchar == ')') /* No path string after the ,. This means the root node */
{
insertnode(numstr,"") ;
continue ;
}

/*OK. tempchar is either 'L' or 'R' followed by ')' */
nextpos = 0 ;
while (tempchar != ')')
{
path[nextpos] = (char)tempchar ;
nextpos++ ;
tempchar = getchar() ;
}
path[nextpos] = '\0' ;
/*Now we have the value for the node and the path. Insert
the node in the tree */
insertnode(numstr, path) ;
}
}

void insertnode(char* valuestr, char* path)
{
int pos = 0 ; /*This variable will be used to track the path */
node* lastnode = NULL ;
node *tmp = NULL ;

/* Traverse the tree as per the path, building and inserting missing
intermediate nodes till the specified node is inserted. */
lastnode = ptr_root ;
while(path[pos] != '\0')
{
if (path[pos] == 'L')
{
if (lastnode->left == NULL) /*The intermediate node
does not exist. Insert it*/
{
tmp = (node *)malloc(sizeof(node)) ;
tmp->value = NULL ;
tmp->left = NULL ;
tmp->right = NULL ;

lastnode->left = tmp ;
}
lastnode = lastnode->left ;
}
else if (path[pos] == 'R')
{
if (lastnode->right == NULL)
{
tmp = (node *)malloc(sizeof(node)) ;
tmp->value = NULL ;
tmp->left = NULL ;
tmp->right = NULL ;

lastnode->right = tmp ;
}
lastnode = lastnode->right ;
}
pos++ ;
}
/*The specified node along with all the intermediate nodes have been inserted.
lastnode points to the specified node */
if (lastnode->value == NULL)
{
lastnode->value = (char*)malloc(strlen(valuestr) + 1) ;
strcpy(lastnode->value, valuestr) ;
}
else
morethanonce = 1;
}

void levelorder()
{
int i = 0 ;
int nextpos = 0 ;

/*initialize node_queue to NULLs */
for (i = 0 ; i < 256 ; i++)
node_queue = (node *)NULL ;
/* first put a pointer to the root in the queue */
node_queue[nextpos] = ptr_root ;
nextpos++ ;

i = 0 ;
while (i < 256 && node_queue != NULL)
{
/*Add the children of node_queue at the end of the queue */
if (node_queue->left != NULL)
{
node_queue[nextpos] = node_queue->left ;
nextpos++ ;
}
if (node_queue->right != NULL)
{
node_queue[nextpos] = node_queue->right ;
nextpos++ ;
}
i++ ;
}
}

int complete()
{
int i = 0;

while (i < 256 && node_queue != NULL)
{
if (node_queue->value == NULL)
return 0 ; /*Incomplete tree */
i++ ;
}
return 1 ; /*Complete tree */
}

void printlevelorder()
{
int i = 0;
printf("%s",node_queue->value) ;

i++ ;
while (i < 256 && node_queue[i] != NULL)
{
printf(" %s", node_queue[i]->value) ;
i++ ;
}
printf("\n") ;
}

Spike
New poster
Posts: 29
Joined: Mon Mar 18, 2002 2:00 am
Location: Washington State
Contact:

122 - WA

I've tried all of the different scenarios I could think of, and I don't think it's a logic problem or anything. Does anyone have any ideas for test data or see any things that might cause a problem?

[java]import java.util.*;

class Main{

static int[] tree = new int[256];
static int nodes = 0;

public static void main( String[] args ){
String g = "", tmp = "";
while( ( tmp = token() ) != null ){
g += tmp;
}
int x = 0;
while( ( x = g.indexOf("()") ) != -1 ){
String w = g.substring(0,x);
g = g.substring( x+2 );
neg();
createTree( w );
}

}

static void createTree( String w ){
StringTokenizer tok = new StringTokenizer(w, "(" );
while( tok.hasMoreTokens() ){
nodes++;
String element = tok.nextToken();
int x = Integer.parseInt( element.substring(0, element.indexOf(",") ) );
int loc = 0;
String bin = "1";
for( int i = element.indexOf(",") + 1 ; i < element.length()-1; i++ ){
if( element.charAt(i) == 'L' ) bin += 0;
else bin += 1;
}
loc = Integer.parseInt( bin, 2 );
loc--;
if( tree[loc] != -1 ){
System.out.println( "not complete" );
return;
}
tree[loc] = x;
}
boolean good = checkTree(0) == nodes;
if( ! good ) System.out.println( "not complete" );
else{
System.out.print( tree[0] );
for( int i = 1; i < tree.length; i++ )
if( tree != -1 ) System.out.print( " " + tree );
System.out.println();
}

}

static int checkTree( int x ){
if( x >= tree.length ) return 0;
if( tree[x] == -1 ) return 0;
return 1 + checkTree( x * 2 + 1 ) + checkTree( x * 2 + 2);
}

static void neg(){
for( int i = 0; i < tree.length; i++) tree = -1;
nodes = 0;
}

static String token( String delim ){
char c = delim.charAt(0);
StringBuffer s = new StringBuffer("");
try{
while( delim.indexOf( (int) c ) != -1 && c != 65535 )
while( delim.indexOf( (int) c ) == -1 && c != 65535 ){
s.append( (char) c );
}
}catch( Exception e ){ return (null); }
if( s.toString().equals("") ) return null;
return s.toString();
}
}
[/java]
Last edited by Spike on Mon Dec 16, 2002 6:44 am, edited 1 time in total.

cym
New poster
Posts: 15
Joined: Mon Oct 14, 2002 3:45 pm
Contact:

HELP

here is my code for 122. I got WA, too.
can anyone give me some test cases or help me with my code???

[cpp]
#include<stdio.h>
#include<string.h>
void main(void)
{
int i,sum,v[256],count=0,ch;
void tree(char tr[257][257],int n[256],int co);

for(i=0;i<256;i++)
v=0;
while((c=getchar())!=-1)
{
if(c=='(')
{
temp=c;
sum=0;
strcpy(t,"");
while((c=getchar())!=')')
{
temp=c;
if(c<58 && c>47)
{
for(i=48;i<58;i++)
if(c==i) break;
sum=sum*10+i-48;
}
if(c=='L')
strcat(t,"L");
if(c=='R')
strcat(t,"R");
}
if(temp=='(' && c==')')
{
count=0;
for(i=0;i<256;i++)
{
v=0;
}
}
else
{
ch=0;
for(i=count;i>0;i--)
{
{
v=v[i-1];
}
else
{
{
v=sum;
ch=1;
break;
}
else
{
{
v=v[i-1];
}
else
{
v[i]=sum;
ch=1;
break;
}
}
}
}
if(ch==0)
{
v[0]=sum;
}
count++;
}
}
}
}

void tree(char tr[257][257],int n[256],int co)
{
int i,j,esc=0;

for(i=0;i<co-1;i++)
{
if(!strcmp(tr[i],tr[i+1]) || n[i]==0 || n[i+1]==0)
{
esc=1;
break;
}
}
if(esc==0)
{
for(i=0;i<co;i++)
{
for(j=0;j<i;j++)
{
esc=1;
if(strlen(tr[j])==strlen(tr[i])-1)
{
if(strlen(tr[j])==0)
{
esc=0;
break;
}
else
{
if(!strncmp(tr[j],tr[i],strlen(tr[j])))
{
esc=0;
break;
}
}
}
}
if(esc==1)
break;
}
}

if(esc==1)
printf("not complete\n");
else
{
for(i=0;i<co;i++)
printf("%d ",n[i]);
printf("\n");
}

}
[/cpp]

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

here's a hint

i tried 122 too, and got WA.
i was sure my program was correct, even thought the judge might be corrupted
then i read the problem again and realize i missed something BIG:

If a tree is not completely specified, i.e., some node in the tree is NOT given a value or a node is given a value more than once, then the string ``not complete'' should be printed.

it took only a few seconds to fix the problem...

cym
New poster
Posts: 15
Joined: Mon Oct 14, 2002 3:45 pm
Contact:

??

but.....epsilon0,
if I don't misunderstand, I don't think my code would neglect what you metioned.
Can you give me some test cases?
or can you try my code and tell me what's wrong?
thx a lot~

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

> (0,L) ()
< 0
>

clearly your program should output "not complete\n", not "0\n". a tree needs a root, right?

i can't see where the error lies within your program because it's unreadable

cym
New poster
Posts: 15
Joined: Mon Oct 14, 2002 3:45 pm
Contact:

....

I fix the bug....but still got WA....><

I also find something strange...
can two nodes have the same value??
ex: (5,) (4,L) (4,R) ()
my code will print 5 4 4

thx for help~~

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
yes, two (or more) nodes can have the same value .... why not ?

If you want to get accepted in this problem, assume that you must have a proper tree after reading all nodes belongs to it. that means:
1) any node within the tree must be defined (must have a value in input)
2) any node can't be defined twice ...

Algorithm is quite simple - read data and build tree )
It's all - if this in not enough - you must have a bug inside your code .

I have a problem with this quesion long time ago - I got RTE first time. But I discovered, that I can't free memory in C. When I commented line which fries memory I got Acepted

Best regards
Dominik

cym
New poster
Posts: 15
Joined: Mon Oct 14, 2002 3:45 pm
Contact:
hmm...dominik
here's my code now
I think it will do what you said, but I got another WA.....
why~~

[c]
#include<stdio.h>
#include<string.h>

void main(void)
{
int i,sum,v[256],count=0,ch;
void tree(char tr[257][257],int n[256],int co);

for(i=0;i<256;i++)
v=0;
while((c=getchar())!=-1)
{
if(c=='(') /*start to catch a node*/
{
temp=c;
sum=0;
strcpy(t,"");
while((c=getchar())!=')') /*while it's not a node's end*/
{
temp=c;
if(c<='9' && c>='0')
{
for(i=48;i<58;i++)
if(c==i) break;
sum=sum*10+i-48;
}
if(c=='L')
strcat(t,"L");
if(c=='R')
strcat(t,"R");
}
if(temp=='(' && c==')') /*if it's the end of a tree*/
{
count=0;
for(i=0;i<256;i++)
{
v=0;
}
}
else /*if it's not the end of a tree*/
{
ch=0;
for(i=count;i>0;i--)
/*the following are insertion sort to sort the nodes */
{
{
v=v[i-1];
}
else
{
{
v=sum;
ch=1;
break;
}
else
{
{
v=v[i-1];
}
else
{
v[i]=sum;
ch=1;
break;
}
}
}
}
if(ch==0)
{
v[0]=sum;
}
count++;
}
}
}
}

/*the function is to check if the input is a valid tree*/

void tree(char tr[257][257],int n[256],int co)
{
int i,j,esc=0;

for(i=0;i<co-1;i++)
{
if(!strcmp(tr[i],tr[i+1]) || n[i]==0 || n[i+1]==0)
{
esc=1;
break;
}
}
if(n[0]==0) esc=1;
if(esc==0)
{
for(i=0;i<co;i++)
{
for(j=0;j<i;j++)
{
esc=1;
if(strlen(tr[j])==strlen(tr[i])-1)
{
if(strlen(tr[j])==0)
{
esc=0;
break;
}
else
{
if(!strncmp(tr[j],tr[i],strlen(tr[j])))
{
esc=0;
break;
}
}
}
}
if(esc==1)
break;
}
}

if(esc==1)
printf("not complete\n");
else
{
for(i=0;i<co;i++)
printf("%d ",n[i]);
printf("\n");
}

}
[/c]
Last edited by cym on Sat Nov 23, 2002 2:33 pm, edited 1 time in total.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
BTW Why don't you use character names instead of numbers ?

Code: Select all

``if((ch >'0') %% (ch < '9')) ``
than

Code: Select all

``if((ch > 49) %% (ch < 58)) ``
I try to check your program afternoon ..... I'm working now and I don't have a C++ compiler to run your code ...

Best regards
Dominik

cym
New poster
Posts: 15
Joined: Mon Oct 14, 2002 3:45 pm
Contact:
you are right...I didn't pay attention to this.....

besides, I think my code can run in a C compiler, like gcc
I just use vc++ to code, but in fact, I use C syntax....

thx for help~~

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
cym: please send me private message with windows-executable file of your code - I send you back tests, on which your program fails ....ok?

sorry, but I have problems with my C++/C compiler

Dominik

cym
New poster
Posts: 15
Joined: Mon Oct 14, 2002 3:45 pm
Contact:
sorry~~
I can't use private message....
can you give me your email??
my email is atias@pchome.com.tw
thx~~