FastPrepRecover a BST by Swapping Two Nodes Back
Problems/Recover a BST by Swapping Two Nodes Back

Recover a BST by Swapping Two Nodes Back

Nutanix logoNutanix● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A report published in September 2017 describes a Nutanix on-campus drive for interns. In the first face-to-face round, the author had to fix a binary search tree in which two nodes had traded places. The fix was to find those two nodes and relink them into their right places. Exchanging their keys alone was not allowed. The author coded it and the interviewer was satisfied.

The report gives no input or output format, key range, examples or limits. Here we chose the following. The tree comes as arrays of keys and left and right child numbers, with -1 for no child, plus the root's number. Keys are distinct integers from -10^9 to 10^9. Two nodes swapping places means each takes the other's place under its parent (or as the root) and the other's children while keeping its own key. The answer is each node's parent in the repaired tree, with -1 for the root. So moving only the keys gives a wrong answer, unless the two nodes are leaves with the same parent. The tree has 2 to 500 nodes.

Our version is about 85% the same as the reported question.

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 (key 50) stays the root;
  • node 6 (key 30) becomes the left child of node 0, and nodes 3 and 4 become its children;
  • node 1 (key 80) becomes the right child of node 2.

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 <= 500
  • keys.length == left.length == right.length == n
  • -10^9 <= keys[i] <= 10^9, and all keys are distinct.
  • Each left[i] and right[i] is -1 or between 0 and n - 1.
  • 0 <= root <= n - 1
  • The arrays describe one binary tree with root root: every other node is a child of exactly one node, and root is 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

Interview reports that mention this question

  • Nutanix Intern Debugging Round and Interviews: 25 Experiences

Nutanix interview experiences

  • Nutanix SWE Intern Phone Screens: 20 Experiences (Part 3 of 3)
  • Nutanix SWE Intern OA Questions: 16 Experiences (Part 2 of 3)
  • Nutanix U.S. SWE Intern Interviews: 54 Experiences (Part 1 of 3)
  • Nutanix SWE OA and Interviews, Level Not Reported: 9 Experiences
All Nutanix interview questionsSee Nutanix hiring insights
Saved
class Solution {
    public int[] recoverTree(int[] keys, int[] left, int[] right, int root) {
        // Write your code here.
    }
}
Checking account…