## 536 - Tree Recovery

Moderator: Board moderators

limelight_team
New poster
Posts: 3
Joined: Sat Dec 29, 2001 2:00 am

### 536 - Tree Recovery

could anybody give me a hint on what algorithm might be used on this problem?

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland
Hi!

This is quite an easy task.

You have to do this using recurence.

in the input the first letter is the root.
If you find this letter in the inord reprezentation you will know the length of the left and right subtree. And now you can do the same with left subtree... ( the second letter in preord is its root)..

And using the recurence you can do it with all tree...

I hope it will help

limelight_team
New poster
Posts: 3
Joined: Sat Dec 29, 2001 2:00 am
Thanks a lot, cyfra, I got p.536 AC'd.

ffkre
New poster
Posts: 3
Joined: Tue Feb 11, 2003 4:13 pm

### 536 get WA. any test case,help~~~~~~~

i got WA, any test case???

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong
[pascal]Deleted as I get accepted[/pascal]

I am not familiar with the binary tree.
Can anyone tell me why I get WA?
I only know that the 1st letter in the pre-order is the root and the total number of path is N-1.
Can anyone give me some sample input/output?

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong
Finally I get accepted.
My array is a little bit (just a '[') too small and cause my counting sort fail.

Grinder
New poster
Posts: 9
Joined: Fri Oct 17, 2003 11:49 am
Contact:
Hi, Can any one help why RUNTIME ERROR:

This is my code:

Code: Select all

``````#include <stdio.h>
#include <string.h>

#define MAX 100

int findRoot(char in[],char item)
{
int i;
for(i = 0; i < strlen(in); i++)
if(in[i] == item)
return i;
return 0;
}

void postfix(char pre[],int pre_low,char in[],int in_low,int in_up)
{
int root;
if(in_low > in_up) return;
if(in_low == in_up)
{
printf("%c",in[in_low]);
return;
}
root = findRoot(in,pre[pre_low]);
if(root > in_low) postfix(pre,pre_low+1,in,in_low,root-1);
if(root < in_up) postfix(pre,root+1,in,root+1,in_up);
printf("%c",in[root]);

}

void main()
{
char prefix[MAX];
char infix[MAX];

while(scanf("%s %s",prefix,infix) == 2)
{
postfix(prefix,0,infix,0,strlen(infix)-1);
printf("\n");
}
}
``````
Plz help me.
I hate three things one- Wrong Answer,TL and the problem which statement is not clear.

Grinder
New poster
Posts: 9
Joined: Fri Oct 17, 2003 11:49 am
Contact:
Hi, Can any one help why RUNTIME ERROR:

This is my code:

Code: Select all

``````#include <stdio.h>
#include <string.h>

#define MAX 100

int findRoot(char in[],char item)
{
int i;
for(i = 0; i < strlen(in); i++)
if(in[i] == item)
return i;
return 0;
}

void postfix(char pre[],int pre_low,char in[],int in_low,int in_up)
{
int root;
if(in_low > in_up) return;
if(in_low == in_up)
{
printf("%c",in[in_low]);
return;
}
root = findRoot(in,pre[pre_low]);
if(root > in_low) postfix(pre,pre_low+1,in,in_low,root-1);
if(root < in_up) postfix(pre,root+1,in,root+1,in_up);
printf("%c",in[root]);

}

void main()
{
char prefix[MAX];
char infix[MAX];

while(scanf("%s %s",prefix,infix) == 2)
{
postfix(prefix,0,infix,0,strlen(infix)-1);
printf("\n");
}
}
``````
Plz help me.
I hate three things one- Wrong Answer,TL and the problem which statement is not clear.

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

### RTEEEEE

hello...
i can't figure out of RTE...

Code: Select all

``ACed...// removed``
thanks.
Last edited by I LIKE GN on Thu Jan 19, 2006 1:08 pm, edited 1 time in total.
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am

Code: Select all

``   if(root < in_up) postfix(pre,root+1,in,root+1,in_up); ``
is wrong.

If anyone is basing your algorithm on his, try the following test case:

Code: Select all

``````ABCEDFGH ECBDFAHG
``````

Johan
New poster
Posts: 7
Joined: Wed Dec 21, 2005 5:27 pm

### 536 wa

Hi,

My 536 passes the example testcase, but a submission results in a wrong answer. Does anybody have a hint or perhaps some nice testcases?

The idea behind the code below is this:

1) The root is first element of the pre-order traversal
2) Everything left of the root in the in-order traversal belongs to the left subtree. Similarly everything to the right belongs to the right subtree.
3) The children of the current root are the first elements of the sub-pre-order-traversals.
4) recurse and put the numbers of the children in an array
5) recurse in post-order traversal through the new tree

Kind regards,

Johan

Code: Select all

``````#include <string>
#include <vector>
#include <cstdlib>
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef vector<vs> vvs;
#define pb push_back
#define sz(v) ((int)(v).size())

vs splitvs(string s,string split)
{
vs uit; string nu;
split+=char(0); s+=char(0);
for(int i=0;i<sz(s);i++)
{
if(split.find(s[i])!=string::npos)
{ if(sz(nu)>0)uit.pb(nu); nu=""; }
else nu+=s[i];
}
return uit;
}

void go(vi left,vi right,int current)
{
if(left[current]!=-1) go(left,right,left[current]);
if(right[current]!=-1) go(left,right,right[current]);
printf("%c",current+64);
}

void fill(vi &left, vi &right, string pre, string in)
{
char root=pre[0];
int r=in.find(root);
string lin=in.substr(0,r), rin=in.substr(r+1), lpre, rpre;

for(int i=1;i<sz(pre);i++)
if(lin.find(pre[i])!=string::npos)
lpre+=pre[i];
else
rpre+=pre[i];

if(sz(lpre)>0)
{
left[root-64]=lpre[0]-64;
fill(left,right,lpre,lin);
}
if(sz(rpre)>0)
{
right[root-64]=rpre[0]-64;
fill(left,right,rpre,rin);
}
}

int main()
{
char buffer[1000];

while(gets(buffer))
{
vs p=splitvs(buffer," ");
if(sz(p)==0)
{ printf("\n"); continue; }
string pre=p[0],in=p[1];
vi left(26,-1), right(26,-1);

//build tree
fill(left,right,pre,in);

//traverse tree
go(left,right,pre[0]-64); printf("\n");
}

return 0;
}
``````
[/code]

Johan
New poster
Posts: 7
Joined: Wed Dec 21, 2005 5:27 pm
Well it worked with only minor changes for a quite similar problem here in the archive, so I'll count the point. Thanks.