11147 - KuPellaKeS BST

[ziliang]

anyone help..

[rushel]

read the description carefully. U have to print each node. worst case running time is O(n^2)

[joeluchoa]

There is some special test case for this problem?
I got WA!
Some hint?
Please!

[emotional blind]

I think there is no special Case..
Problem Description is very much clear;

One hint I can give you from Problem description:
# If a node has a left child, all values in the left subtree are less than or equal to the value of the value of the node itself.
# If a node has a right child, all values in the right subtree are strictly greater than the value of the node itself.

[sm_hosein]

Try it:

8
1
0
6
0 0 0 0 0 0
2
-1 1
4
-1 1 -1 1
5
-10 2 2 3 3
6
3 3 2 1 1 -10
9
-4 -3 -2 -1 0 1 2 3 4
10
5 4 3 2 1 -1 -2 -3 -4 -5

My AC Code's Answer:

Case #1: 0
Case #2: 0(0(0(0(0(0)))))
Case #3: -1(1)
Case #4: 1(-1(-1,1))
Case #5: 3(3(-10(2(2))))
Case #6: 3(3(-10(1(1,2))))
Case #7: -4(4(-3(3(-2(2(-1(1(0))))))))
Case #8: -5(5(-4(4(-3(3(-2(2(-1(1)))))))))

[little joey]

I don't get it. From the description

The difference between sum of all values in the left subtree and sum of all values in the right subtree is minimum.

In your case 4, your answer is 1(-1(-1,1)): sum of left subtree = -1, sum of right subtree = 0, so difference = -1 - 0 = -1.
But for this BST: -1(-1,(1(1))) the sum of left subtree = -1, sum of right subtree = 2, so difference = -1 - 2 = -3, which is smaller than your solution.
And for the first sample I also can get a better solution than the one given...

[Ilham Kurnia]

I don't get it. From the description

The difference between sum of all values in the left subtree and sum of all values in the right subtree is minimum.

In your case 4, your answer is 1(-1(-1,1)): sum of left subtree = -1, sum of right subtree = 0, so difference = -1 - 0 = -1.
But for this BST: -1(-1,(1(1))) the sum of left subtree = -1, sum of right subtree = 2, so difference = -1 - 2 = -3, which is smaller than your solution.
And for the first sample I also can get a better solution than the one given...

I think the intended meaning is that the absolute difference of the two subtrees is as small as possible.

[joeluchoa]

Try it:

8
1
0
6
0 0 0 0 0 0
2
-1 1
4
-1 1 -1 1
5
-10 2 2 3 3
6
3 3 2 1 1 -10
9
-4 -3 -2 -1 0 1 2 3 4
10
5 4 3 2 1 -1 -2 -3 -4 -5

My AC Code's Answer:

Case #1: 0
Case #2: 0(0(0(0(0(0)))))
Case #3: -1(1)
Case #4: 1(-1(-1,1))
Case #5: 3(3(-10(2(2))))
Case #6: 3(3(-10(1(1,2))))
Case #7: -4(4(-3(3(-2(2(-1(1(0))))))))
Case #8: -5(5(-4(4(-3(3(-2(2(-1(1)))))))))

in the third case, could it be 1(-1)???

[joeluchoa]

I got AC now, however I continue with doubts!

[joeluchoa]

Now I understood my mistake!
The third case can't be 1(-1) because the left subtree sum must be maximal!

Silly error!

[TimeString]

Try it:

4
-1 1 -1 1

My AC Code's Answer:

Case #4: 1(-1(-1,1))

sort input -1 1 -1 1 -> -1 -1 1 1
does it means root=1, and left subtree={-1,-1,1}, and right subtree={<empty>}, and then left sum=-1 , right sum=0, difference=1?

but my solution is:
parent=-1 , left subtree={<empty>} , right subtree={-1,1,1}, and then left sum=0 , and right sum=1, which difference is also 1, but the sum of left subtree is bigger than above.

did i misunderstand something??

[neno_uci]

If a node has a right child, all values in the right subtree are strictly greater than the value of the node itself.

So you can't have -1 as root and then -1 in it's right subtree.

[sclo]

I don't know of any special case. I think the sample input is good enough.