Show problems as
Classic problem #99MediumTreeDepth-First SearchBinary Search TreeBinary Tree

Recover Binary Search Tree

Real-world version: Repair the Swapped Labels
Tracked in this browser only
Read Recover Binary Search Tree on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A card index is filed as a search tree of distinct labels: for every card, every label in its left branch is smaller than the card's own and every label in its right branch is larger.

A clerk peeled the labels off exactly two cards and stuck each one on the other card. The shape of the index was not touched, only those two labels, and the index no longer files correctly.

The index arrives as shelf, a tier-by-tier listing. shelf[0] is the root card's label. The rest of the list is consumed two entries at a time, taking cards in the order they were listed: the next two entries are that card's left-branch and right-branch labels, and null means that branch is empty, so it contributes no entries of its own. Trailing nulls are omitted.

Swap the two labels back so the index files correctly again. Exactly one pair of labels can be exchanged to achieve this. Change the labels in place in shelf -- do not build a new listing and do not move any card -- and return shelf.

Examples

Example 1

Input
shelf = [20, 10, 30, null, 25, 15]
Output
[20, 10, 30, null, 15, 25]

The labels 25 and 15 trade places. Afterwards 15 sits in the right branch of 10 and below 20, and 25 sits in the left branch of 30 and above 20, so every branch holds the labels it should.

Example 2

Input
shelf = [2, 3, 1]
Output
[2, 1, 3]

The root 2 has 3 in its left branch and 1 in its right branch. Exchanging those two labels puts the smaller one on the left and the larger one on the right.

Example 3

Input
shelf = [8, 3, 5]
Output
[5, 3, 8]

The root's label 8 is larger than the 5 in its right branch. Exchanging them leaves 5 at the root, with 3 on its left and 8 on its right.

Example 4

Input
shelf = [1, 2]
Output
[2, 1]

The left branch holds 2 while the root holds 1, so the two labels trade places.

Constraints

  • The number of cards in the index is in the range [2, 1000].
  • -2^31 <= card label <= 2^31 - 1
  • All labels are distinct, and exactly two of them were exchanged.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def recover_tree(shelf: list) -> list:
Java
public Integer[] recoverTree(Integer[] shelf)

More on the same topics