## 10821 - Constructing BST

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Programmer
New poster
Posts: 9
Joined: Sun Mar 13, 2005 11:41 am

### 10821 - Constructing BST

Hello.
I'm trying to solve this problem.Can anyone give some hint how to solve it.
Thanks.
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm
[1.....N]

now let 1<=K<=N then

if you insert K first then in the left subtree you have to accommodate K-1 elements and N-K-1 elements in the right subtree within a height of <=H-1

now check if you can have a subtree of height <=H-1 with K-1 elements and also N-K-1 elements... for every K, starting from 1, check the possibility and whenever its possible try the samething for each subtree with height decreasing by 1 for each level...

hope it helps.
Programmer
New poster
Posts: 9
Joined: Sun Mar 13, 2005 11:41 am
Thanks Dreamer#1 I solve it.
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

i guess this problem cannot have any tricky inputs so maybe i have missed something basic ..Can someone check this I/O please..

Code: Select all

``````30 5
30 30
50 30
50 6
60 7
4 1
10000 30
0 0

``````

Code: Select all

``````Case 1: 15 7 3 1 2 5 4 6 11 9 8 10 13 12 14 23 19 17 16 18 21 20 22 27 25 24 26 29 28 30
Case 2: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Case 3: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 35 27 26 31 29 28 30 33 32 34 43 39 37 36 38 41 40 42 47 45 44 46 49 48 50
Case 4: 19 3 1 2 11 7 5 4 6 9 8 10 15 13 12 14 17 16 18 35 27 23 21 20 22 25 24 26 31 29 28 30 33 32 34 43 39 37 36 38 41 40 42 47 45 44 46 49 48 50
Case 5: 1 29 13 5 2 3 4 9 7 6 8 11 10 12 21 17 15 14 16 19 18 20 25 23 22 24 27 26 28 45 37 33 31 30 32 35 34 36 41 39 38 40 43 42 44 53 49 47 46 48 51 50 52 57 55 54 56 59 58 60
Case 6: Impossible
Case 7: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1809 17 18 785 273 19 145 81 49 33 25 21 20 23 22 24 29 27 26 28 31 30 32 41 37 35 34 36 39 38 40 45 43 42 44 47 46 48 65 57 53 51 50 52 55 54 56 61 59 58 60 63 62 64 73 69 67 66 68 71 70 72 77 75 74 76 79 78 80 113 97 89 85 83 82 84 87 86 88 93 91 90 92 95 94 96 105 101 99 98 100 103 102 104 109 107 106 108 111 110 112 129 121 117 115 114 116 119 118 120 125 123 122 124 127 126 128 137 133 131 130 132 135 134 136 141 139 138 140 143 142 144 209 177 161 153 149 147 146 148 15.............

``````
[/code]
if u can think of it .. u can do it in software.
mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Your output is correct, but you missed period after the word "Impossible"
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA
Thanx
if u can think of it .. u can do it in software.
james299
New poster
Posts: 10
Joined: Tue Jul 26, 2005 8:58 am
Location: Taiwan

hi !
I'm trying to solve this problem .
I use the alog just like what Dreamer#1 did, but I got WA for serveral times.And now I can't find out what's wrong with my code.
1. I check the input N & H, if N is over 2^H-1 or less than H, and print impossible.
2. And I use recursion to build the tree.
3. I use preorder to traverse the tree, and print each one.
4. I check the space ' ' at the tail of my output.

and my program I/O

Code: Select all

``````30 5
30 30
50 30
50 6
60 7
4 1
10000 30
0 0
``````

Code: Select all

``````Case 1: 15 7 3 1 2 5 4 6 11 9 8 10 13 12 14 23 19 17 16 18 21 20 22 27 25 24 26 29 28 30
Case 2: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Case 3: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 35 27 26 31 29 28 30 33 32 34 43 39 37 36 38 41 40 42 47 45 44 46 49 48 50
Case 4: 19 3 1 2 11 7 5 4 6 9 8 10 15 13 12 14 17 16 18 35 27 23 21 20 22 25 24 26 31 29 28 30 33 32 34 43 39 37 36 38 41 40 42 47 45 44 46 49 48 50
Case 5: 1 29 13 5 2 3 4 9 7 6 8 11 10 12 21 17 15 14 16 19 18 20 25 23 22 24 27 26 28 45 37 33 31 30 32 35 34 36 41 39 38 40 43 42 44 53 49 47 46 48 51 50 52 57 55 54 56 59 58 60
Case 6: Impossible.
Case 7: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1809 .......
``````
here are my part of bulidtree code

Code: Select all

``````struct MyTree* buildTree( int N , int H , int inti ) {
struct MyTree *left = NULL , *right = NULL , *nowptr;
/* tree */
int i ;
if(H==1&&N==1)
return newItem(inti+1);
/* at the root */
if(H<=0)
return NULL;
/* just in case */
for( i = 1 ; i <= N ; i ++ )
if(isTree(i-1,H-1)==1&&isTree(N-i,H-1)==1) {
/* isTree is a method check that N is samller than 2^H*/
if(i!=1) {
left = buildTree(i-1,H-1,inti);
if(left==NULL)
continue;
}
if(i!=N) {
right = buildTree(N-i,H-1,inti+i);
if(right==NULL) {
free(left);
continue;
}
}
nowptr = newItem(inti+i);
nowptr->left = left ;
nowptr->right = right ;
return nowptr;
}/* for */
return NULL;
}
``````
here are my main function

Code: Select all

`````` while(scanf("%d %d",&N,&H)!=EOF&&N+H!=0) {
if(isTree(N,H)==1&&N>=H) {
topptr = buildTree(N,H,0);
if(topptr!=NULL) {
printf("Case %d:",times++);
PrintLev(topptr);
printf("\n");
}
else
printf("Case %d: Impossible.\n",times++);
}
else
printf("Case %d: Impossible.\n",times++);
}
``````
Thanks you guys spend your precious time.
Please point out my err.[/code]
mysword
New poster
Posts: 26
Joined: Sun Mar 06, 2005 8:52 am

### 10821, help

what's wrong???????

Code: Select all

``````ac now:)
``````
Last edited by mysword on Fri Sep 23, 2005 9:00 am, edited 1 time in total.
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### Re: 10821, help

mysword wrote:what's wrong???????
Your solution's not working for

Code: Select all

``````1 2
0 0``````
The output should be

Code: Select all

``Case 1: 1``
mysword
New poster
Posts: 26
Joined: Sun Mar 06, 2005 8:52 am

### Re: 10821, help

Martin Macko wrote:
mysword wrote:what's wrong???????
Your solution's not working for

Code: Select all

``````1 2
0 0``````
The output should be

Code: Select all

``Case 1: 1``
Thank you very much!!!!
moham_87
New poster
Posts: 2
Joined: Mon Jul 31, 2006 1:23 pm
Location: Egypt
1. I check the input N & H, if N is over 2^H-1 or less than H, and print impossible.
why should u check if N is less than H? I think if N<H, it should work
The problem statement says:
In this problem, you have to find the order of 1 to N integers such that the BST constructed by them has height of at most H.
good luck