Back to DSA

Recover Binary Search Tree

hard
Acceptance: 40%
BSTBinary Tree

Two nodes in a binary search tree have had their values accidentally swapped, violating the BST property. Identify the two misplaced nodes and swap their values back to restore the tree, keeping the tree structure unchanged.

Examples

Example 1:
Input:root = [5,1,null,null,4]
Output:[5,4,null,null,1]
Example 2:
Input:root = [2,4,1]
Output:[2,1,4]

Hints

Related Problems

Maximum Depth of Binary TreeeasyInvert Binary TreeeasyValidate Binary Search TreemediumLowest Common Ancestor of a Binary TreemediumBinary Tree Level Order Traversalmedium
00:00
class Solution {
    private TreeNode first = null, second = null, prev = null;

    public void recoverTree(TreeNode root) {
        inorder(root);
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }

    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);
    }
}
Time complexityO(n)
Space complexityO(h)