Correct BST with two nodes swapped

Intuition

To fix a BST with two swapped nodes, the key is to recognize that an inorder traversal of a BST yields a sorted sequence. First, collect the node values using an inorder traversal, which will provide an array of values. Sorting this array reveals what the inorder sequence should be if the BST were correct. By comparing the BST's actual inorder traversal with this sorted array, it's possible to identify where the nodes are out of order. The task then is to correct these discrepancies by updating the BST nodes with the appropriate values from the sorted array, thereby restoring the BST's correct structure without altering its overall form.

Approach

Perform an inorder traversal of the BST to gather the node values into an array. Sort this array to get the correct inorder sequence of the BST.
Traverse the BST again using inorder traversal, comparing each node's value with the corresponding value in the sorted array.
When a mismatch is found between a node's value and the value from the sorted array, update the BST node with the correct value from the sorted array.
Return the modified BST.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    void recoverTree(TreeNode* root) {
        // Initialize variables to keep track of the nodes to be swapped
        TreeNode *first = nullptr, *second = nullptr, *prev = nullptr;

        // Helper function for inorder traversal
        function<void(TreeNode*)> inorder = [&](TreeNode* node) {
            if (!node) return;

            // Traverse the left subtree
            inorder(node->left);

            // Identify the nodes that are out of order
            if (prev && prev->data > node->data) {
                if (!first) first = prev;
                second = node;
            }

            // Update prev node to the current node
            prev = node;

            // Traverse the right subtree
            inorder(node->right);
        };

        // Perform the inorder traversal to find the two nodes
        inorder(root);

        // Swap the values of the two nodes to correct the BST
        if (first && second) {
            swap(first->data, second->data);
        }
    }
};

// Helper function to insert nodes in the tree for testing purposes
TreeNode* insertLevelOrder(vector<int>& arr, int i) {
    if (i >= arr.size() || arr[i] == -1) return nullptr;
    TreeNode* root = new TreeNode(arr[i]);
    root->left = insertLevelOrder(arr, 2 * i + 1);
    root->right = insertLevelOrder(arr, 2 * i + 2);
    return root;
}

// Helper function to print inorder traversal of the tree
void inorderPrint(TreeNode* root) {
    if (root) {
        inorderPrint(root->left);
        cout << root->data << " ";
        inorderPrint(root->right);
    }
}

int main() {
    // Example input tree: [1, 3, -1, -1, 2]
    vector<int> nodes = {1, 3, -1, -1, 2};
    TreeNode* root = insertLevelOrder(nodes, 0);

    // Solution instance
    Solution sol;
    sol.recoverTree(root);

    // Print corrected tree
    inorderPrint(root);

    return 0;
}
/**
 * Definition for a binary tree node.
 */
public class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { data = val; left = null; right = null; }
}

class Solution {
    // Initialize variables to keep track of the nodes to be swapped
    private TreeNode first = null, second = null, prev = null;

    public void recoverTree(TreeNode root) {
        // Perform the inorder traversal to find the two nodes
        inorder(root);

        // Swap the values of the two nodes to correct the BST
        if (first != null && second != null) {
            int temp = first.data;
            first.data = second.data;
            second.data = temp;
        }
    }

    private void inorder(TreeNode node) {
        if (node == null) return;

        // Traverse the left subtree
        inorder(node.left);

        // Identify the nodes that are out of order
        if (prev != null && prev.data > node.data) {
            if (first == null) first = prev;
            second = node;
        }

        // Update prev node to the current node
        prev = node;

        // Traverse the right subtree
        inorder(node.right);
    }

    // Main method to demonstrate the solution
    public static void main(String[] args) {
        // Example input tree: [1, 3, null, null, 2]
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.left.right = new TreeNode(2);

        // Solution instance
        Solution sol = new Solution();
        sol.recoverTree(root);

        // Helper function to print inorder traversal of the tree
        inorderPrint(root);
    }

    private static void inorderPrint(TreeNode root) {
        if (root != null) {
            inorderPrint(root.left);
            System.out.print(root.data + " ");
            inorderPrint(root.right);
        }
    }
}
# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.data = val
        self.left = left
        self.right = right

class Solution:
    def recoverTree(self, root):
        """
        Recovers a binary search tree where two nodes have been swapped by mistake.
        
        :param root: TreeNode, the root of the binary search tree
        """
        
        # Initialize variables to keep track of the nodes to be swapped
        self.first = self.second = self.prev = None
        
        def inorder(node):
            """
            Performs an inorder traversal to find the two swapped nodes.
            
            :param node: TreeNode, the current node in the traversal
            """
            if not node:
                return
            
            # Traverse the left subtree
            inorder(node.left)
            
            # Identify the nodes that are out of order
            if self.prev and self.prev.data > node.data:
                if not self.first:
                    self.first = self.prev
                self.second = node
            
            # Update prev node to the current node
            self.prev = node
            
            # Traverse the right subtree
            inorder(node.right)
        
        # Perform the inorder traversal to find the two nodes
        inorder(root)
        
        # Swap the values of the two nodes to correct the BST
        if self.first and self.second:
            self.first.data, self.second.data = self.second.data, self.first.data

# Main method to run the solution
if __name__ == "__main__":
    # Helper function to insert nodes in the tree for testing purposes
    def insertLevelOrder(arr, root, i, n):
        if i < n:
            temp = TreeNode(arr[i])
            root = temp
            root.left = insertLevelOrder(arr, root.left, 2 * i + 1, n)
            root.right = insertLevelOrder(arr, root.right, 2 * i + 2, n)
        return root
    
    # Example input tree: [1, 3, null, null, 2]
    nodes = [1, 3, None, None, 2]
    root = None
    root = insertLevelOrder(nodes, root, 0, len(nodes))
    
    # Solution instance
    sol = Solution()
    sol.recoverTree(root)
    
    # Helper function to print inorder traversal of the tree
    def inorderPrint(root):
        if root:
            inorderPrint(root.left)
            print(root.data, end=' ')
            inorderPrint(root.right)
    
    # Print corrected tree
    inorderPrint(root)
/**
 * Definition for a binary tree node.
 */
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.data = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    recoverTree(root) {
        // Initialize variables to keep track of the nodes to be swapped
        this.first = null;
        this.second = null;
        this.prev = null;

        // Helper function for inorder traversal
        const inorder = (node) => {
            if (!node) return;

            // Traverse the left subtree
            inorder(node.left);

            // Identify the nodes that are out of order
            if (this.prev && this.prev.data > node.data) {
                if (!this.first) this.first = this.prev;
                this.second = node;
            }

            // Update prev node to the current node
            this.prev = node;

            // Traverse the right subtree
            inorder(node.right);
        };

        // Perform the inorder traversal to find the two nodes
        inorder(root);

        // Swap the values of the two nodes to correct the BST
        if (this.first && this.second) {
            let temp = this.first.data;
            this.first.data = this.second.data;
            this.second.data = temp;
        }
    }
}

// Helper function to insert nodes in the tree for testing purposes
function insertLevelOrder(arr, i) {
    if (i >= arr.length || arr[i] === null) return null;
    let root = new TreeNode(arr[i]);
    root.left = insertLevelOrder(arr, 2 * i + 1);
    root.right = insertLevelOrder(arr, 2 * i + 2);
    return root;
}

// Helper function to print inorder traversal of the tree
function inorderPrint(root) {
    if (root) {
        inorderPrint(root.left);
        process.stdout.write(root.data + ' ');
        inorderPrint(root.right);
    }
}

// Main method to demonstrate the solution
function main() {
    // Example input tree: [1, 3, null, null, 2]
    let nodes = [1, 3, null, null, 2];
    let root = insertLevelOrder(nodes, 0);

    // Solution instance
    let sol = new Solution();
    sol.recoverTree(root);

    // Print corrected tree
    inorderPrint(root);
    console.log();
}

main();

Complexity Analysis

Time Complexity : O(N), where N is the number of nodes in the tree. The inorder traversal is performed once, visiting each node exactly once.

Space Complexity : O(H), where H is the height of the tree. The recursive call stack will have a maximum depth of H, which is the height of the tree.

Intuition

A Binary Search Tree (BST) has an inorder traversal that results in a sorted sequence. When two elements are swapped, this sorted order is disrupted. To identify these misplaced nodes, traverse the tree and keep track of the previous and next nodes for each visited node. By doing this, it's possible to detect where the order is violated. Once these violations are identified, the algorithm can pinpoint the two nodes that are out of place, whether they are adjacent or not. This allows for the correct nodes to be swapped, restoring the BST's proper structure.

Approach

Use four pointers: first, prev, middle, and last. first and middle help identify the misplaced nodes, prev tracks the previous node during the inorder traversal, and last marks the second node of the misplaced pair if the nodes are not adjacent.
Perform an inorder traversal of the BST, comparing each node's value with the previous node's value (prev) to detect any violations where the current node's value is less than the previous node's value. When a violation is found:
- The first violation identifies the first and middle nodes. The first node is the first element encountered that is not greater than its previous node, and the middle node is temporarily stored in case the swapped nodes are adjacent.
- If a second violation occurs, it indicates that the swapped nodes are not adjacent, and the last node is identified.
- If no second violation is found, implying that the swapped nodes are adjacent, the middle node identified earlier is retained.
Once the misplaced nodes are identified, perform the necessary swaps based on whether the nodes are adjacent or not:
- If both first and last are identified, swap the values of the first and last nodes.
- If only first and middle are identified, swap their values.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode *first = nullptr, *middle = nullptr, *last = nullptr, *prev = nullptr;

        // Helper function for inorder traversal
        function<void(TreeNode*)> inorder = [&](TreeNode* node) {
            if (!node) return;

            // Traverse the left subtree
            inorder(node->left);

            // Identify the nodes that are out of order
            if (prev && prev->data > node->data) {
                if (!first) {
                    first = prev;  // First out-of-order node
                    middle = node; // Middle node in case nodes are adjacent
                } else {
                    last = node;   // Last out-of-order node
                }
            }

            prev = node; // Update prev node to the current node
            inorder(node->right); // Traverse the right subtree
        };

        inorder(root); // Perform the inorder traversal to find the two nodes

        // Correct the BST by swapping the misplaced nodes
        if (first && last) {
            swap(first->data, last->data); // Non-adjacent nodes
        } else if (first && middle) {
            swap(first->data, middle->data); // Adjacent nodes
        }
    }
};

// Helper function to insert nodes in the tree for testing purposes
TreeNode* insertLevelOrder(vector<int>& arr, int i) {
    if (i >= arr.size() || arr[i] == -1) return nullptr;
    TreeNode* root = new TreeNode(arr[i]);
    root->left = insertLevelOrder(arr, 2 * i + 1);
    root->right = insertLevelOrder(arr, 2 * i + 2);
    return root;
}

// Helper function to print inorder traversal of the tree
void inorderPrint(TreeNode* root) {
    if (root) {
        inorderPrint(root->left);
        cout << root->data << " ";
        inorderPrint(root->right);
    }
}

int main() {
    // Example input tree: [1, 3, -1, -1, 2]
    vector<int> nodes = {1, 3, -1, -1, 2};
    TreeNode* root = insertLevelOrder(nodes, 0);

    // Solution instance
    Solution sol;
    sol.recoverTree(root);

    // Print corrected tree
    inorderPrint(root);

    return 0;
}
/**
 * Definition for a binary tree node.
 */
public class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { data = val; left = null; right = null; }
}

class Solution {
    private TreeNode first = null, middle = null, last = null, prev = null;

    public void recoverTree(TreeNode root) {
        inorder(root); // Perform inorder traversal to identify the misplaced nodes

        // Correct the BST by swapping the misplaced nodes
        if (first != null && last != null) {
            int temp = first.data;
            first.data = last.data;
            last.data = temp;
        } else if (first != null && middle != null) {
            int temp = first.data;
            first.data = middle.data;
            middle.data = temp;
        }
    }

    private void inorder(TreeNode node) {
        if (node == null) return;

        // Traverse the left subtree
        inorder(node.left);

        // Identify the nodes that are out of order
        if (prev != null && prev.data > node.data) {
            if (first == null) {
                first = prev;  // First out-of-order node
                middle = node; // Middle node in case nodes are adjacent
            } else {
                last = node;   // Last out-of-order node
            }
        }

        prev = node; // Update prev node to the current node

        // Traverse the right subtree
        inorder(node.right);
    }

    // Main method to demonstrate the solution
    public static void main(String[] args) {
        // Example input tree: [1, 3, null, null, 2]
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.left.right = new TreeNode(2);

        // Solution instance
        Solution sol = new Solution();
        sol.recoverTree(root);

        // Helper function to print inorder traversal of the tree
        inorderPrint(root);
    }

    private static void inorderPrint(TreeNode root) {
        if (root != null) {
            inorderPrint(root.left);
            System.out.print(root.data + " ");
            inorderPrint(root.right);
        }
    }
}
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.data = val
        self.left = left
        self.right = right

class Solution:
    def __init__(self):
        # Initialize the pointers
        self.first = None
        self.first_next = None
        self.last = None
        self.previous_node = TreeNode(float('-inf'))  # Previous node initialized to negative infinity

    def inorderTraversal(self, root: TreeNode):
        if not root:
            return
        
        # Traverse the left subtree
        self.inorderTraversal(root.left)

        # Identify misplaced nodes
        if self.previous_node and root.data < self.previous_node.data:
            if not self.first:
                self.first = self.previous_node  # First out-of-order node
                self.first_next = root  # Node next to the first out-of-order node
            else:
                self.last = root  # Second out-of-order node

        # Update previous node to current node
        self.previous_node = root

        # Traverse the right subtree
        self.inorderTraversal(root.right)

    def recoverTree(self, root: TreeNode):
        # Reset the pointers
        self.first = self.first_next = self.last = None
        self.previous_node = TreeNode(float('-inf'))
        
        # Perform the inorder traversal to find the two nodes
        self.inorderTraversal(root)

        # Correct the BST by swapping the misplaced nodes
        if self.first and self.last:
            self.first.data, self.last.data = self.last.data, self.first.data  # Non-adjacent nodes
        elif self.first and self.first_next:
            self.first.data, self.first_next.data = self.first_next.data, self.first.data  # Adjacent nodes

# Helper function to insert nodes in the tree for testing purposes
def insertLevelOrder(arr, i):
    if i >= len(arr) or arr[i] is None:
        return None
    root = TreeNode(arr[i])
    root.left = insertLevelOrder(arr, 2 * i + 1)
    root.right = insertLevelOrder(arr, 2 * i + 2)
    return root

# Helper function to print inorder traversal of the tree
def inorderPrint(root):
    if root:
        inorderPrint(root.left)
        print(root.data, end=' ')
        inorderPrint(root.right)

if __name__ == "__main__":
    # Example input tree: [1, 3, None, None, 2]
    nodes = [1, 3, None, None, 2]
    root = insertLevelOrder(nodes, 0)

    # Solution instance
    sol = Solution()
    sol.recoverTree(root)

    # Print corrected tree
    inorderPrint(root)
/**
 * Definition for a binary tree node.
 */
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.data = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    constructor() {
        // Initialize the pointers
        this.first = null;
        this.firstNext = null;
        this.last = null;
        this.previousNode = new TreeNode(Number.NEGATIVE_INFINITY); // Previous node initialized to negative infinity
    }

    inorderTraversal(node) {
        if (!node) return;

        // Traverse the left subtree
        this.inorderTraversal(node.left);

        // Identify misplaced nodes
        if (this.previousNode && node.data < this.previousNode.data) {
            if (!this.first) {
                this.first = this.previousNode;  // First out-of-order node
                this.firstNext = node;          // Node next to the first out-of-order node
            } else {
                this.last = node;                // Second out-of-order node
            }
        }

        // Update previous node to the current node
        this.previousNode = node;

        // Traverse the right subtree
        this.inorderTraversal(node.right);
    }

    recoverTree(root) {
        // Reset the pointers
        this.first = this.firstNext = this.last = null;
        this.previousNode = new TreeNode(Number.NEGATIVE_INFINITY);
        
        // Perform the inorder traversal to find the two nodes
        this.inorderTraversal(root);

        // Correct the BST by swapping the misplaced nodes
        if (this.first && this.last) {
            [this.first.data, this.last.data] = [this.last.data, this.first.data];  // Non-adjacent nodes
        } else if (this.first && this.firstNext) {
            [this.first.data, this.firstNext.data] = [this.firstNext.data, this.first.data];  // Adjacent nodes
        }
    }
}

// Helper function to insert nodes in the tree for testing purposes
function insertLevelOrder(arr, i) {
    if (i >= arr.length || arr[i] === null) return null;
    const root = new TreeNode(arr[i]);
    root.left = insertLevelOrder(arr, 2 * i + 1);
    root.right = insertLevelOrder(arr, 2 * i + 2);
    return root;
}

// Helper function to print inorder traversal of the tree
function inorderPrint(root) {
    if (root) {
        inorderPrint(root.left);
        process.stdout.write(root.data + ' ');
        inorderPrint(root.right);
    }
}

// Main function to demonstrate the solution
const main = () => {
    // Example input tree: [1, 3, null, null, 2]
    const nodes = [1, 3, null, null, 2];
    const root = insertLevelOrder(nodes, 0);

    // Solution instance
    const sol = new Solution();
    sol.recoverTree(root);

    // Print corrected tree
    inorderPrint(root);
};

main();

Complexity Analysis

Time Complexity : O(N), traverses the binary tree once.

Space Complexity : O(N), in the worst case, the function call stack can go up to the depth of the tree, which is N nodes in an unbalanced tree.

Problem List

Correct BST with two nodes swapped

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code