Problem Link
Author: Ivan Safonov
Tester: Hasan Jaddouh
Editorialist: Bhuvnesh Jain
Difficulty
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)
