Identify Swapped BST Nodes | Dataford Interview Questions

Two nodes of a binary search tree have been swapped; find (and fix) them.

Asked in the onsite round 1 stage. Whiteboard coding.

Represent the tree as a level-order array using heap indexing: the children of index i are 2*i+1 and 2*i+2; missing nodes are None. Implement recover_bst(values) to restore the BST in place and return the array. Node values are distinct.

Example 1: values = [3, 1, 4, None, None, 2] returns [2, 1, 4, None, None, 3].

Example 2: values = [1, 3, None, None, 2] returns [3, 1, None, None, 2].

Constraints: 2 <= len(values) <= 1000; the structure is a valid binary tree; exactly two values were swapped.

Constraints

2 <= len(values) <= 1000
values contains integers or None
The non-None entries represent a valid binary tree
All node values are distinct
Exactly two node values were swapped

Function Signature

def recover_bst(values):

Your question is Identify Swapped BST Nodes. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem