TREESORT - Editorial

Practice

Contest

Author: Ivan Safonov

Editorialist: Bhuvnesh Jain

EASY-MEDIUM

Prerequisites

Intersection of segments, Depth First Search

Problem

Given a binary tree with N nodes and L leaves. Each leaf has a distinct number x (1 ≤ x ≤ L) written on it. We sort the leaves in order of pre-order traversal. We also want the numbers written on the leaves to be in sorted order. So, we can perform some operations where we can swap the left and right child of a node. Find the minimum number of operations to achieve the target.

Explanation

Let us first understand how the leaves are sorted. If you know about pre-order traversal of tree, it is clear the leaves are in the same order as in pre-order traversal. It can be stated as flattening the tree from left to right direction and the leaves arrange themselves in the same order. Below is an illustration of the same.

Now, we can think of 2 ways to approach the problem. One is to solve the problem bottom-up and other is to solve it top-down. In the latter, it might happen that the swaps we do at some initial stages might lead to situations where either we apply swap again or there is no possible swap left although a solution exists. If you are not clear with the last statement, don’t worry. Read the solution using bottom-up approach below and think again about the statement. The idea of bottom-up also applies as it is closer to the way the leaves are sorted as in pre-order traversal.

So, let us try to solve the problem in bottom-up manner. This means we go to the leaves in the same order as they should appear in the final list. Also, we will solve the problem for left and right subtree recursively and then try to find the answer for the full tree. Let me illustrate the meaning through an example.

When we are dealing with node (A-D), we find the answer for left and right son. This means if the left son can’t be sorted, so the whole tree can’t be sorted as well. This applies to the right child as well. If the left and right child can be sorted, it means now the full subtree moves as a full block. This means to find whether the node (A-D) can be sorted based on the left and right sons, we need to check first if a swap is required or not. A swap will be required if the smallest number in left son is greater than the smallest number in the second son. Suppose we perform the above swap operation, if applicable. Now we need to quickly check if the whole tree is sorted or not. This means all leaves in the subtree of the left son should be less than all leaves in the subtree of the right son. Equivalently, if the largest leaf in left son should be less than the smallest leaf in the right son.

The above observation implies that we need to store the minimum and maximum value of leaves in a subtree and then we can use it to determine if a swap is required and then if the tree can be sorted at that point. Below figure shows the above process for next step.

The main idea for the bottom-up approach was to understand that swapping left and right sons make all the leaves in them move in blocks and if they are not in correct order, the final tree can’t be in right order.

Below is a small pseudo-code with the above logic:

``````
# Assume the (min, max) range for the subtree is stored in vals.

# solve returns -1 if the tree can't be sorted at given node
# else it returns minimum number of swaps.
def solve(node):
if is_leaf(node):
# leaf value is already sorted
vals[node] = {leaf_value, leaf_value}
return 0

else:
lft = solve(left_son(node))
rgt = solve(right_son(node))

if lft == -1 or rgt == -1:
# can't sort the left or right son
return -1

if left_son(node).max < right_son(node).min:
# no swap is required and tree will be sorted.
vals[node] = {left_son(node).min, right_son(node).max}
return lft + rgt

else if left_son(node).min > rigth_son(node).max:
# Greedily perform swap and tree will be sorted
vals[node] = {right_son(node).min, left_son(node).max}
return lft + rgt + 1

else:
# Even after swapping, some number in left son are
# greater than some number in right son. So tree
# can't be sorted.
return -1

``````

The time complexity of the above approach will be O(N) per test case. This is because we visit each node once and do O(1) operation of each node (calculating the min and max of the subtree, checking whether a swap is required and then if the tree is sorted at that node). This is enough to solve the problem for all subtasks.

For more details, you can refer to the editorialist’s solution for help.

Bonus Problem

In the problem, it was already stated that 1 is always the root of the binary tree. If the same format of the input is given and it is not necessary that 1 is the root of the tree, how will you find the root of the tree to apply the above algorithm?

Feel free to share your approach, if it was somewhat different.

Time Complexity

O(N) per test case.

Space Complexity

O(N)

Setter’s solution

Tester’s solution

Editorialist solution

3 Likes

Hi @likecs,@vijju123,@isaf27,
I followed the same approach but instead of checking min & max i checked the same by checking taking difference of 1 as it should be true if the subtree is sorted and following the constraint of pairwise distinct and 1<=r<= L for leaf nodes.

Please check my implementation once and let me know where i get it wrong. Or even any test case for which my code produce wrong output is also appreciable.

https://www.codechef.com/viewsolution/19029454

how to analyze input in form of tree like to draw it in form of a tree? Could anyone help?

@shivamgor498 because if there is intersection of the children’s (min,max) range then swapping them will have some lower value in the right child(although it will be sorted).For example if left child min-max pair is (1,3) and right child min-max pair is (2,4) then swapping them will make 1 go in right child and 2 go in left child again making it unfeasible because since 2 was in right child and 3 was in left child therefore we sorted but again reached the same dilemma. therefore the segment should not intersect.
Solution(submitted again with comments)->CodeChef: Practical coding for everyone

Hello, thank you for the editorial. Can you please help me with a test case in which my code is failing? I had used the approach in the editorial. So I am really confused where I am going wrong. I also tried various cases for an hour before giving up.

Thanks a lot for your help.

https://www.codechef.com/viewsolution/19030569

Try tree[idx].ll, tree[idx].rr and see, you will spot the issue with the first test case.

1 Like

still didn’t get it.

3 Likes

Can anyone give explanation why top down approach fails or any test case ? @likecs @vijju123 @praveenkumar12

1 Like

For the bonus problem which the Editorialist put forward:

We could maintain something like a parent array which holds the information about the node whose son it is. After completely scanning the input, we could randomly pick a node and move up the parent array until its God parent is detected. The node which we end up now, will be the root node and we will solve this problem rooting with this node.

``````Pseudocode: (Modifications only)
for i = 1 to N:
parent[i] = i
for i = 1 to N:
scan L,R
if(L != -1):
#usual code
parent[L] = parent[R] = i
else:
#usual code
root=1
while(parent[root] != root):
root = parent[root]
solve(root)
``````

Time Complexity for finding root: O(logN)

where the worst case would be randomly selecting a leaf node and moving all the way up in logN steps.

I hope this approach works.

1 Like

Can anyone help not albe to find where code fails.Did almost same as editorialist @likecs.

@atharva_sarage, did you consider the case that the tree may not be perfectly balanced?
ie) left child = leaf and right a tree or vice versa. The condition still needs to be satisfied even if one side is a tree.

@tamiliit I have considered the above condition.

Can someone please explain setter’s solution? I am not able to understand the meaning of statement :
if (kol[p] != mx[p] - mn[p] + 1) ok = false;
TIA.

Hey, I still couldn’t understand the problem statement. How the strings are LL,RL,RR and how the input is converted to a binary tree. Can anyone please explain it properly, that would be really helpful !

The question is interesting

@likecs In question the constraints has N>=2 but if N=2 then its impossible to build the tree because in question there is mentioned that “non-leaf: has exactly two sons — a left son and a right son”,for root is doesn’t satisfy, am i right to point it out?
Still its a interesting question

Please convert this input into tree
5
3 5
-1 2
2 4
-1 3
-1 1

1 is the root.each line gives 2 children l and r or l=-1 means it’s a leaf.

So 1st line 3,5. so node 3,5 are children of 1. 2nd line is -1,2. so 2nd node is a leaf with value 2. 3 line is 2,4. so 3rd node has chilren 2,4 and so on.

got it thank you!

Try debugging your code for some test cases. Take this one-

``````Input
1
3
2 3
-1 5
-1 7