Recover Binary Search Tree - Practice Coding Problems

Recover Binary Search Tree - Problem

You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

A binary search tree satisfies the property that for every node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater than the node's value.

Your task is to identify the two swapped nodes and correct their values to restore the BST property.

Input & Output

Example 1 — Adjacent Swap

$ Input: root = [1,3,null,null,2]

› Output: [3,1,null,null,2]

💡 Note: The values 1 and 3 were swapped. After correction: 3 should be root with 1 as left child and 2 as right child of 1.

Example 2 — Non-Adjacent Swap

$ Input: root = [3,1,4,null,null,2]

› Output: [2,1,4,null,null,3]

💡 Note: Values 3 and 2 were swapped. The BST should have 2 as root, with 1 as left child and 4 as right child, and 3 as left child of 4.

Constraints

The number of nodes in the tree is in the range [2, 1000]
-2³¹ ≤ Node.val ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input

BST with two nodes swapped: [1,3,null,null,2]

Process

Detect violations in inorder sequence

Output

Corrected BST: [3,1,null,null,2]

Key Takeaway

🎯 Key Insight: Use inorder traversal to detect BST violations - exactly two nodes will be out of order

Asked in

a Amazon 15 M Microsoft 12 G Google 8

The key insight is that inorder traversal of a BST should give a sorted sequence. When two nodes are swapped, this sequence will have violations. The optimal approach uses a single DFS traversal to detect the violation points and swap the problematic nodes. Time: O(n), Space: O(h)

Common Approaches

Approach	Time	Space	Notes
✓ Inorder Traversal + Sorting	O(n log n)	O(n)	Extract all values, sort them, then update tree nodes accordingly
Two-Pass DFS (Morris-like)	O(n)	O(h)	Single pass to identify both swapped nodes, then swap their values

Inorder Traversal + Sorting — Algorithm Steps

Step 1: Inorder traversal to collect all values
Step 2: Sort the collected values
Step 3: Inorder traversal again to assign sorted values back

Visualization

Tap to expand

Step-by-Step Walkthrough

Collect Values

Inorder traversal gives [1,3,2]

Sort Values

Sorted array becomes [1,2,3]

Update Tree

Assign sorted values back to nodes

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int values[1000];
int valueCount = 0;
int updateIndex = 0;

void inorderCollect(struct TreeNode* node) {
    if (node) {
        inorderCollect(node->left);
        values[valueCount++] = node->val;
        inorderCollect(node->right);
    }
}

void inorderUpdate(struct TreeNode* node) {
    if (node) {
        inorderUpdate(node->left);
        node->val = values[updateIndex++];
        inorderUpdate(node->right);
    }
}

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

void solution(struct TreeNode* root) {
    if (!root) return;
    
    valueCount = 0;
    updateIndex = 0;
    
    // Collect values
    inorderCollect(root);
    
    // Sort values
    qsort(values, valueCount, sizeof(int), compare);
    
    // Update tree
    inorderUpdate(root);
}

int main() {
    // For this implementation, we'll assume a simple case
    struct TreeNode* root = createNode(1);
    root->left = createNode(3);
    root->right = createNode(2);
    
    solution(root);
    
    printf("[%d,%d,%d]\n", root->val, root->left->val, root->right->val);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

O(n) for two traversals plus O(n log n) for sorting

⚡ Linearithmic

Space Complexity

O(n)

Array to store all n node values plus O(h) recursion stack

⚡ Linearithmic Space

182.0K Views

Medium Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Inorder Traversal + Sorting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler