Problem
Two nodes of a BST were swapped by mistake. Recover the tree without changing its structure.
Example
Input: [1,3,null,null,2]
Output: [3,1,null,null,2]Solution
In-order traversal yields a sorted sequence. The two out-of-order positions reveal the swapped nodes.
def recover_tree(root):
first = second = prev = None
def inorder(node):
nonlocal first, second, prev
if not node: return
inorder(node.left)
if prev and prev.val > node.val:
if not first: first = prev
second = node
prev = node
inorder(node.right)
inorder(root)
first.val, second.val = second.val, first.valfunction recoverTree(root) {
let first = null, second = null, prev = null;
function inorder(node) {
if (!node) return;
inorder(node.left);
if (prev && prev.val > node.val) {
if (!first) first = prev;
second = node;
}
prev = node;
inorder(node.right);
}
inorder(root);
[first.val, second.val] = [second.val, first.val];
}class Solution {
TreeNode *first = nullptr, *second = nullptr, *prev = nullptr;
void inorder(TreeNode* node) {
if (!node) return;
inorder(node->left);
if (prev && prev->val > node->val) {
if (!first) first = prev;
second = node;
}
prev = node;
inorder(node->right);
}
public:
void recoverTree(TreeNode* root) {
inorder(root);
swap(first->val, second->val);
}
};private TreeNode first = null, second = null, prev = null;
public void recoverTree(TreeNode root) {
inorder(root);
int tmp = first.val;
first.val = second.val;
second.val = tmp;
}
private void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left);
if (prev != null && prev.val > node.val) {
if (first == null) first = prev;
second = node;
}
prev = node;
inorder(node.right);
}Complexity
- Time: O(n)
- Space: O(h)
Explanation
In-order traversal of a valid BST is sorted. With one swap, you see at most two violations: first = the larger of the first violation, second = the smaller of the (possibly second) violation.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?