Fixing Two nodes of a BST

Time: O(n)

Space: O(h)

Intuition

Find two swapped nodes in BST in-order traversal. In sorted in-order, swapped nodes appear as violations. First violation: first > second. Second violation: third > fourth (or same pair).

Algorithm

1In-order traversal, track previous node.
2First violation (prev > curr): first = prev, second = curr.
3Second violation (prev > curr): second = curr (update second only).
4Swap values of first and second.

Common Pitfalls

•If only one violation, nodes are adjacent in in-order. If two violations, first was from first violation, second from second.

Fixing Two nodes of a BST.java

Java

// Approach: In-order traversal. Find the two swapped nodes (first: curr < prev violation, second: last such violation).
// Swap their values.
// Time: O(n) Space: O(h)
class Node {
    int data;
    Node left;
    Node right;

    Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

class Solution {
    Node a = null;
    Node b = null;
    Node prev = null;

    public void helper(Node root) {
        if (root == null)
            return;
        helper(root.left);
        if (prev != null && prev.data > root.data) {
            if (a == null)
                a = prev;
            b = root;
        }
        prev = root;
        helper(root.right);
    }

    void correctBST(Node root) {
        helper(root);
        int temp = a.data;
        a.data = b.data;
        b.data = temp;
    }
}

Was this solution helpful?