Loading...
Loading...
Loading...
Rohan built a correct binary search tree of seat numbers for an exam hall. Then a bug swapped the values of exactly two nodes. The shape of the tree did not change.
Find the two swapped values and swap them back. Print the two values in increasing order. Then print the fixed tree in level order.
N for no node. Children are listed only for real nodes, and N tokens at the end of the line may be left out. For example, 2 N 1 N N is 2 with right child 1.N for every missing child of a real node.Example 1
Input
50 60 70 20 40 30 80 N N N N N N N N
Output
30 60 50 30 70 20 40 60 80 N N N N N N N N
30 and 60 were swapped. 60 sits in the left subtree of 50, and 30 in the right subtree.
Example 2
Input
2 N 1 N N
Output
1 2 1 N 2 N N
Two nodes: 1 must be the root and 2 its right child.
Try the problem first. Open one hint at a time.
An in-order walk of a correct tree gives the values in increasing order. What does the swap do to that order?
Look for places where a value is larger than the one after it. There are one or two such drops.
The first wrong value is the larger value at the first drop. The second is the smaller value at the last drop.
Remember the two nodes during the walk, swap their values, then print the tree.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor