# Problem Link

Practice

Contest

Author: Ivan Safonov

Tester: Hasan Jaddouh

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.

![|200x300](upload://aN5to3N1HHEexL3UkWjbtvvyYol.png)

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.

![|600x250](upload://vgg8UiTc8WulMLBpgwPMGcLYnyr.png)

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.

![|600x250](upload://8E7v4gSbGMPw7fQAE6mycvJ2y1a.png)

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.

O(N)

# Solution Links

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)->https://www.codechef.com/viewsolution/19032939

Read about vectors. Refer to geeeksforgeeks for BFS and DFS implementations.

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

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

@ruddradev, in your print statement, you are printing tree[idx].rr, tree[idx].rr

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

1 Like

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!

still didn’t get it.

3 Likes

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

``````Input
1
3
2 3
-1 5
-1 7
Your Output
-1
Correct Output
0 //All leaves already sorted.
``````

Find few more test cases like that and debug using them.

1 Like

Thanks for looking into the code. But the input that you give is invalid according to constraints as it is given in contraints for any child r is less than equal to number of leafs. So in this case L =2

So only possible values for childs is 1 and 2 not 5 and 7.

Oh…lol xD. I didnt use that constraint anywhere in my solution, so kind of missed that.

@ruddradev … I Was not able to implement it in contest but now if you are still stuck you can see my solution. It’s implemented exactly as stated in editorial.

solution link

1 Like

Just look at `possible` variable in your code. And check this test case-

``````Input
2
7
2 3
4 5
6 7
-1 1
-1 4
-1 3
-1 2
5
3 5
-1 2
2 4
-1 3
-1 1
Your Output
-1
-1
Expected Output
-1
1
``````
1 Like

Thanks @vijju123, It was a silly mistake, I didn’t reset the boolean flag for every test case which i used to check if the solution is possible or not.

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.

Your approach is Ok, but the time complexity is wrong. It should be O(N) as there is no restriction that the binary tree is balanced. It can be skewed as well. For another easy approach, you can refer to my solution. The idea is that the number which doesn’t occur in the input is the root of the tree (The proof is easy and left as an exercise).