Two swapped keys
A catalogue index is kept as a binary search tree: at each node all keys of the left subtree are smaller than its key, and all keys of the right one larger. After a write failure two nodes may have had their keys swapped; the shape of the tree itself, all the links to children, survived. Or nothing may have happened. Check the index: if it is fine, print OK, otherwise find the two swapped keys.
The third and fourth tests are an index by time of the 2025 earthquakes from the USGS catalogue, the key being seconds since the start of 2015. In the third the tree was built by inserting the shocks from strongest to weakest, in the fourth by time, and it stretched into a chain of more than two thousand nodes.
Input
The first line holds n (2 ≤ n ≤ 10⁵), the number of nodes. The next n lines describe nodes 1, 2, …, n: the key (an integer from 1 to 10⁹, all keys distinct) and the numbers of the left and right child (0 if there is no child). The root is node 1. The input tree is guaranteed to be either a search tree or obtained from one by swapping the keys of exactly two nodes.
Output
OK or the two swapped keys separated by a space, the smaller first.
Examples
Example 1
7 50 2 3 30 4 5 70 6 7 20 0 0 40 0 0 60 0 0 80 0 0
OK
Example 2
7 50 2 3 70 4 5 30 6 7 20 0 0 40 0 0 60 0 0 80 0 0
30 70
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 11 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Checking each node only against its children is not enough: in the first sample, if 50 and 40 are swapped, the root 40 and its left child 30 with right child 50 are each fine on their own, but the tree is not. Which traversal of a search tree outputs the keys in increasing order?
2Hint 2
The in-order traversal: left subtree, node, right subtree. What does an increasing sequence with two elements swapped look like? How many places does it have where the next element is smaller than the previous?
3The idea
A tree is a search tree if and only if its in-order traversal is strictly increasing. Swapping two keys breaks the increase in one place if the keys were neighbours in order, and in two places if they were not. The swapped ones are the left element of the first descent and the right element of the last.
4Walkthrough
Suppose in a sorted sequence the elements at positions i < j were swapped. The large element ended up at position i and is larger than its right neighbour: that is the first descent. The small one ended up at position j and is smaller than its left neighbour: that is the last descent. There are no other descents: the other neighbours stand in their original order. If j = i + 1, both descents are the same place.
The traversal is a loop with an explicit stack: go left pushing nodes onto the stack, pop a node, record its key and move to the right subtree. Recursion is dangerous here: in the fourth test the tree is more than two thousand deep, in the eighth 80,000, while Python stops at depth 1000 by default.
4+Solution
5Complexity
O(n) time and O(n) memory for the sequence and the stack. You can manage with O(height) memory too, by comparing each key with the previous one in the traversal at once, without keeping the whole sequence.
6Common mistakes
- Both keys from the first descent. Right only if the swapped keys are neighbours in order. In the second sample the traversal gives 20, 70, 40, 50, 60, 30, 80: there are two descents, and the swapped keys are 70 and 30, not 70 and 40.
- A parent–child check. The search tree rule concerns all keys of a subtree, not just the children.
- A recursive traversal. On a chain of 80,000 nodes it crashes in Python with a recursion depth error.
- Output order. The smaller key first.