Recover a BST by Swapping Two Nodes Back
Updated
Problem statement
A binary tree has n nodes numbered from 0 to n - 1. Node i has the key keys[i], its left child is node left[i] and its right child is node right[i], where -1 means there is no such child. The root is node root. All keys are distinct.
The tree used to be a valid binary search tree: for every node, all keys in its left subtree were smaller than its key and all keys in its right subtree were larger. Then exactly two different nodes swapped places. Each of the two took over the other's position, meaning the other's place under its parent (or the root position) and the other's children, while keeping its own key. If one of the two was the parent of the other, the child moved up and the parent moved down.
Swap the two nodes back, moving the nodes themselves rather than exchanging their keys. Return an array parent of length n, where parent[i] is the number of node i's parent in the repaired tree, or -1 if node i is the root of the repaired tree.
Every key stays with its node, so the answer shows whether the nodes really moved: exchanging only the two keys leaves every parent as it was, which is wrong in every case except one. When the two swapped nodes are both leaves with the same parent, moving them and exchanging their keys give the same parents, so either way is accepted there. In the repaired tree the keys follow search-tree order, so each node's parent also determines whether the node is a left or a right child.
Function
recoverTree(keys: int[], left: int[], right: int[], root: int) → int[]Examples
Example 1
keys = [50,80,70,20,40,60,30]left = [1,3,5,-1,-1,-1,-1]right = [2,4,6,-1,-1,-1,-1]root = 0return = [-1,2,0,6,6,2,0]The nodes with keys 30 (node 6) and 80 (node 1) traded places. Node 1 sits where 30 belongs, as the left child of the root with children 3 and 4, while node 6 sits where 80 belongs, as the right child of node 2. Swapping the two nodes back gives:
- node
0(key50) stays the root; - node
6(key30) becomes the left child of node0, and nodes3and4become its children; - node
1(key80) becomes the right child of node2.
So the parents are [-1,2,0,6,6,2,0]. Just exchanging the keys 30 and 80 would leave every parent as it is now, [-1,0,0,1,1,2,2], which is not accepted.
Example 2
keys = [15,5,10,12,20]left = [1,-1,3,-1,-1]right = [2,-1,4,-1,-1]root = 0return = [2,2,-1,0,0]The root (node 0, key 15) and its right child (node 2, key 10) were swapped. Swapping them back moves node 2 up to the root and node 0 down to its right child. Node 1 (key 5) becomes the left child of node 2, and nodes 3 and 4 (keys 12 and 20) become the children of node 0. The parents are [2,2,-1,0,0].
Example 3
keys = [-7,3]left = [1,-1]right = [-1,-1]root = 0return = [1,-1]The root has key -7 but its left child has the larger key 3. Swapping the two nodes makes node 1 the root and node 0 its left child, so the parents are [1,-1].
Constraints
2 <= n <= 500keys.length == left.length == right.length == n-10^9 <= keys[i] <= 10^9, and all keys are distinct.- Each
left[i]andright[i]is-1or between0andn - 1. 0 <= root <= n - 1- The arrays describe one binary tree with root
root: every other node is a child of exactly one node, androotis no node's child. - The tree is a valid binary search tree in which exactly two different nodes swapped places, as described above.
More Nutanix Onsite Interview questions
- Design Hit CounterONSITE INTERVIEW · Seen Oct 2026
- Peak Process MemoryONSITE INTERVIEW · Seen Aug 2026
- Minimum Operations to Transform ArrayONSITE INTERVIEW · Seen Jun 2026
- Count Connected Components in an Undirected GraphONSITE INTERVIEW · Seen Aug 2025
- LRU CacheONSITE INTERVIEW · Seen Aug 2025
- Running Median of a Multilevel Linked List in Level OrderONSITE INTERVIEW · Seen Aug 2025
- Custom Array IteratorONSITE INTERVIEW · Seen Dec 2024
- Collapse Runs of Repeated CharactersONSITE INTERVIEW · Seen Nov 2022
- Anagram Words in a SentenceONSITE INTERVIEW · Seen Apr 2022
- Sudoku SolverONSITE INTERVIEW · Seen Feb 2022
Similar questions at other companies
- N-ary Index-Path Encoder and DecoderBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Delete Nodes and Return Forest RootsGoogle · ONSITE INTERVIEWGoogle interview questions
- Render a Task Tree from CSV RowsStripe · PHONE SCREEN · ONSITE INTERVIEWStripe interview questions
- Filter Undesired Comments and Their DescendantsReddit · PHONE SCREEN · ONSITE INTERVIEWReddit interview questions
- JSON Path Lookup with Implicit Array WildcardsMongoDB · ONSITE INTERVIEWMongoDB interview questions
- Maximum Sum Among Longest Root-to-Leaf PathsAmazon · ONSITE INTERVIEW
- Delete and Compact a Forest SubtreePinterest · PHONE SCREEN · ONSITE INTERVIEWPinterest interview questions
- Onion-Peel Layers of a Binary TreeeBay · ONSITE INTERVIEWeBay interview questions
- Match a Descendant Selector in a DOM TreeMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Serialize and Deserialize an N-Ary TreeUber · ONSITE INTERVIEWUber interview questions