Recover BST - Two Nodes are Swapped, Correct it

Last Updated : 12 Oct, 2025

Given the root of a Binary Search Tree (BST) where two nodes have been swapped, restore the tree so that it satisfies the BST property.

Examples:

Input:

file

Output: [[6], [2, 10], [1, 3, 7, 12]]
Explanation: After swapping the node 10 and 2. The tree satisfies the BST property.

2

Input:

420046840

Output: [[2], [2, 3]]
Explanation: After swapping nodes 1 and 2, the tree becomes valid BST.

420046839
Try it on GfG Practice
redirect icon

Table of Content

[Naive Approach] Using Inorder Traversal and Sorting - O(n * log n) Time and O(n) Space

The idea is to use the property of BST: an inorder traversal of a valid BST gives elements in sorted order. First, traverse the tree and store all node values in an array. Since exactly two nodes are swapped so that array will not be fully sorted. Sort the array to get the correct order of elements. Finally, traverse the tree again in inorder fashion, and replace each node’s value with the corresponding value from the sorted array. This restores the original BST structure while maintaining all other nodes in place.

C++ 
//Driver Code Starts
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

// Node structure
class Node{
  public:
    int data;
    Node* left;
    Node* right;
    Node(int x){
        data = x;
        left = right = nullptr;
    }
};

// Calculate  Height
int getHeight(Node* root, int h) {
    if (root == nullptr) return h - 1;
    return max(getHeight(root->left, h + 1), 
                       getHeight(root->right, h + 1));
}

// Print Level Order
void levelOrder(Node* root) {
    queue<pair<Node*, int>> q;
    q.push({root, 0});

    int lastLevel = 0;

    // function to get the height of tree
    int height = getHeight(root, 0);

    // printing the level order of tree
    while (!q.empty()) {
        auto top = q.front(); q.pop();
        Node* node = top.first;
        int lvl = top.second;

        if (lvl > lastLevel) {
            cout << "
";
            lastLevel = lvl;
        }

        // all levels are printed
        if (lvl > height) break;

        
        if (node->data != -1) cout << node->data << " ";
        
        // printing null node
        else cout << "N ";

        // null node has no children
        if (node->data == -1) continue;

        if (node->left == nullptr) q.push({new Node(-1), lvl + 1});
        else q.push({node->left, lvl + 1});

        if (node->right == nullptr) q.push({new Node(-1), lvl + 1});
        else q.push({node->right, lvl + 1});
    }
}
//Driver Code Ends


// Function to store the inorder traversal 
void findInorder(Node* curr, vector<int>&inorder){
    if(curr == nullptr) return;

    findInorder(curr->left, inorder);

    inorder.push_back(curr->data);
    findInorder(curr->right, inorder);
}

// Recursive function to correct the BST by replacing
// node values with sorted values
void correctBSTUtil(Node* root, vector<int> &inorder, int &index){
    if(root == nullptr) return;
    correctBSTUtil(root->left, inorder, index);
    root->data = inorder[index];
    index++;
    correctBSTUtil(root->right, inorder, index);
}

// Function to fix the given BST 
void correctBST(Node* root){
    vector<int> inorder;
    findInorder(root, inorder);
    sort(inorder.begin(), inorder.end());
  
    int index = 0;
    correctBSTUtil(root, inorder, index);
}



//Driver Code Starts

int main(){
  
    // Constructing the tree with swapped nodes
    //       6
    //     /  \
    //    10   2
    //   / \  / \
    //  1  3 7  12
  
    Node *root = new Node(6);
    root->left = new Node(10);
    root->right = new Node(2);
    root->left->left = new Node(1);
    root->left->right = new Node(3);
    root->right->right = new Node(12);
    root->right->left = new Node(7);

    correctBST(root);
    levelOrder(root);
 
    return 0;
}
//Driver Code Ends
Java 
//Driver Code Starts
import java.util.*;

class Node {
    int data;
    Node left, right;

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

class GfG {
    
      // calculate Height
     static int getHeight( Node root, int h ) {
        if( root == null ) return h-1;
        
        return Math.max(getHeight(root.left, h+1), 
                                     getHeight(root.right, h+1));
    }
    // calculate Height
    // Print Level Order
     static void levelOrder(Node root) {
        Queue<List<Object>> queue = new LinkedList<>();
        queue.offer(List.of(root, 0));
        
        int lastLevel = 0;
        
        // function to get the height of tree
        int height = getHeight(root, 0);
        
        // printing the level order of tree
        while( !queue.isEmpty()) {
            List<Object> top = queue.poll();
            
            Node node = (Node) top.get(0);
            int lvl = (int) top.get(1);
            
            if( lvl > lastLevel ) {
                System.out.println();
                lastLevel = lvl;
            }
            
            // all levels are printed
            if( lvl > height ) break;
            
            // printing null node
            System.out.print((node.data == -1 ? "N" : node.data) + " ");
            
            // null node has no children
            if( node.data == -1 ) continue;
            
            if( node.left == null ) queue.offer(List.of(new Node(-1), lvl+1));
            else queue.offer(List.of(node.left, lvl+1));
            
            if( node.right == null ) queue.offer(List.of(new Node(-1), lvl+1));
            else queue.offer(List.of(node.right, lvl+1));
        }
    }
//Driver Code Ends

  
    // Function to store the inorder traversal 
    static void findInorder(Node curr, ArrayList<Integer> inorder) {
        if (curr == null) return;
        findInorder(curr.left, inorder);
        inorder.add(curr.data);
        findInorder(curr.right, inorder);
    }

    // Recursive function to correct the BST by replacing
	// node values with sorted values
    static void correctBSTUtil(Node root, ArrayList<Integer> inorder, 
                               		int[] index) {
        if (root == null) return;
        correctBSTUtil(root.left, inorder, index);
        root.data = inorder.get(index[0]);
        index[0]++;
        correctBSTUtil(root.right, inorder, index);
    }
	
  	// Function to fix the given BST 
    static void correctBST(Node root) {
        ArrayList<Integer> inorder = new ArrayList<>();
        findInorder(root, inorder);
        Collections.sort(inorder);

        int[] index = {0};
        correctBSTUtil(root, inorder, index);
    }

   


//Driver Code Starts
    public static void main(String[] args) {
        // Constructing the tree with swapped nodes
        //       6
        //     /  \
        //    10   2
        //   / \  / \
        //  1  3 7  12
        // Here, 10 and 2 are swapped

        Node root = new Node(6);
        root.left = new Node(10);
        root.right = new Node(2);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
        root.right.right = new Node(12);
        root.right.left = new Node(7);

        correctBST(root);
        levelOrder(root);
    }
}

//Driver Code Ends
Python 
#Driver Code Starts
from collections import deque

class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None



#   calculate Height
def getHeight(root, h):
    if root is None:
        return h - 1
    return max(getHeight(root.left, h + 1), getHeight(root.right, h + 1))
# Print Level Order
def levelOrder(root):
    queue = deque([[root, 0]])
    lastLevel = 0

    # function to get the height of tree
    height = getHeight(root, 0)

    # printing the level order of tree
    while queue:
        node, lvl = queue.popleft()

        if lvl > lastLevel:
            print()
            lastLevel = lvl

        # all levels are printed
        if lvl > height:
            break

        # printing null node
        print("N" if node.data == -1 else node.data, end=" ")

        # null node has no children
        if node.data == -1:
            continue

        if node.left is None:
            queue.append([Node(-1), lvl + 1])
        else:
            queue.append([node.left, lvl + 1])

        if node.right is None:
            queue.append([Node(-1), lvl + 1])
        else:
            queue.append([node.right, lvl + 1])

#Driver Code Ends


# Function to store the inorder
# traversal 
def findInorder(curr, inorder):
    if curr is None:
        return
    findInorder(curr.left, inorder)
    inorder.append(curr.data)
    findInorder(curr.right, inorder)


# Recursive function to correct the BST by replacing
# node values with sorted values
def correctBSTUtil(root, inorder, index):
    if root is None:
        return
    correctBSTUtil(root.left, inorder, index)
    root.data = inorder[index[0]]
    index[0] += 1
    correctBSTUtil(root.right, inorder, index)

# Function to fix the given BST 
def correctBST(root):
    inorder = []
    findInorder(root, inorder)
    inorder.sort()

    index = [0]
    correctBSTUtil(root, inorder, index)


#Driver Code Starts


if __name__ == "__main__":
    
    # Constructing the tree with swapped nodes
    #       6
    #     /  \
    #    10   2
    #   / \  / \
    #  1  3 7  12

    root = Node(6)
    root.left = Node(10)
    root.right = Node(2)
    root.left.left = Node(1)
    root.left.right = Node(3)
    root.right.right = Node(12)
    root.right.left = Node(7)

    correctBST(root)
    levelOrder(root)

#Driver Code Ends
C# 
//Driver Code Starts
using System;
using System.Collections.Generic;

// Node structure
public class Node {
    public int data;
    public Node left;
    public Node right;
    public Node(int x) {
        data = x;
        left = right = null;
    }
}

public class GFG {

   //Calculate Height
    static int getHeight(Node root, int h) {
        if (root == null) return h - 1;
        return Math.Max(getHeight(root.left, h + 1), 
                               getHeight(root.right, h + 1));
    }

    // Print Level Order
    static void levelOrder(Node root) {
        if (root == null) return;

        Queue<(Node, int)> queue = new Queue<(Node, int)>();
        queue.Enqueue((root, 0));

        int lastLevel = 0;
        int height = getHeight(root, 0);

        while (queue.Count > 0) {
            var (node, lvl) = queue.Dequeue();

            if (lvl > lastLevel) {
                Console.WriteLine();
                lastLevel = lvl;
            }

            // Stop printing if all levels are done
            if (lvl > height) break;

            // print null node
            Console.Write((node.data == -1 ? "N" : node.data.ToString()) + " ");

            // null node has no children
            if (node.data == -1) continue;

            if (node.left == null) queue.Enqueue((new Node(-1), lvl + 1));
            else queue.Enqueue((node.left, lvl + 1));

            if (node.right == null) queue.Enqueue((new Node(-1), lvl + 1));
            else queue.Enqueue((node.right, lvl + 1));
        }
    }
//Driver Code Ends

    
    // Function to store the inorder traversal
    static void findInorder(Node curr, List<int> inorder) {
        if (curr == null) return;
        findInorder(curr.left, inorder);
        inorder.Add(curr.data);
        findInorder(curr.right, inorder);
    }

    // Recursive function to correct the BST by replacing
    // node values with sorted values
    static void correctBSTUtil(Node root, List<int> inorder, ref int index) {
        if (root == null) return;
        correctBSTUtil(root.left, inorder, ref index);
        root.data = inorder[index];
        index++;
        correctBSTUtil(root.right, inorder, ref index);
    }

    // Function to fix the given BST
    static void correctBST(Node root) {
        List<int> inorder = new List<int>();
        findInorder(root, inorder);

        // Sort inorder array since two nodes are swapped
        inorder.Sort();

        int index = 0;
        correctBSTUtil(root, inorder, ref index);
    }



//Driver Code Starts

    static void Main() {
        
        // Constructing the tree with swapped nodes
        //       6
        //     /  \
        //    10   2
        //   / \  / \
        //  1  3 7  12

        Node root = new Node(6);
        root.left = new Node(10);
        root.right = new Node(2);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
        root.right.left = new Node(7);
        root.right.right = new Node(12);
        correctBST(root);
        levelOrder(root);
    }
}

//Driver Code Ends
JavaScript 
//Driver Code Starts
// Node structure
class Node {
    constructor(x) {
        this.data = x;
        this.left = this.right = null;
    }
}

// Queue node for custom queue implementation
class QNode {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

// Custom Queue implementation
class Queue {
    constructor() {
        this.front = null;
        this.rear = null;
    }

    isEmpty() {
        return this.front === null;
    }

    enqueue(x) {
        let newNode = new QNode(x);
        if (this.rear === null) {
            this.front = this.rear = newNode;
            return;
        }
        this.rear.next = newNode;
        this.rear = newNode;
    }

    dequeue() {
        if (this.front === null) return null;

        let temp = this.front;
        this.front = this.front.next;

        if (this.front === null) this.rear = null;

        return temp.data;
    }
}

// Calculate Height
function getHeight(root, h) {
    if (root === null) return h - 1;
    return Math.max(getHeight(root.left, h + 1), getHeight(root.right, h + 1));
}

// Print Level Order
function levelOrder(root) {
    let queue = new Queue();
    queue.enqueue([root, 0]);

    let lastLevel = 0;
    let height = getHeight(root, 0);

    while (!queue.isEmpty()) {
        let [node, lvl] = queue.dequeue();

        if (lvl > lastLevel) {
            console.log("");
            lastLevel = lvl;
        }

        // all levels are printed
        if (lvl > height) break;

        // print null node
        process.stdout.write((node.data === -1 ? "N" : node.data) + " ");

        // null node has no children
        if (node.data === -1) continue;

        if (node.left === null) queue.enqueue([new Node(-1), lvl + 1]);
        else queue.enqueue([node.left, lvl + 1]);

        if (node.right === null) queue.enqueue([new Node(-1), lvl + 1]);
        else queue.enqueue([node.right, lvl + 1]);
    }
}
//Driver Code Ends


// Function to store the inorder traversal
function findInorder(curr, inorder) {
    if (curr == null) return;
    findInorder(curr.left, inorder);
    inorder.push(curr.data);
    findInorder(curr.right, inorder);
}

// Recursive function to correct the BST by replacing
// node values with sorted values
function correctBSTUtil(root, inorder, index) {
    if (root == null) return;
    correctBSTUtil(root.left, inorder, index);
    root.data = inorder[index.value];
    index.value++;
    correctBSTUtil(root.right, inorder, index);
}

// Function to fix the given BST
function correctBST(root) {
    let inorder = [];
    findInorder(root, inorder);
    inorder.sort((a, b) => a - b);

    let index = { value: 0 };
    correctBSTUtil(root, inorder, index);
}


//Driver Code Starts
// Driver Code

// Constructing the tree with swapped nodes
//       6
//     /  \
//    10   2
//   / \  / \
//  1  3 7  12


let root = new Node(6);
root.left = new Node(10);
root.right = new Node(2);
root.left.left = new Node(1);
root.left.right = new Node(3);
root.right.left = new Node(7);
root.right.right = new Node(12);
correctBST(root);
levelOrder(root);

//Driver Code Ends

Output
6 
2 10 
1 3 7 12

[Expected Approach] Using One Traversal - O(n) Time and O(h) Space

In a BST, two nodes are swapped so, there are two possible scenarios:

Swapped nodes are adjacent in inorder traversal:

  • In this case, the inorder traversal of the BST will show only one violation (a pair of nodes where the previous node’s value is greater than the current node’s value).
  • To track this, we use three pointers: first, middle, and last, along with a prev pointer.
  • When the violation is detected, update first to point to the previous node and middle to the current node.
  • Since there is only one violation, swapping first and middle will restore the BST.

Swapped nodes are not adjacent in inorder traversal:

  • Here, the inorder traversal will show two violations.
  • During traversal, the first violation sets first and middle. The second violation updates the last pointer to the current node.
  • Finally, swapping the values of first and last restores the BST correctly.
C++ 
//Driver Code Starts
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

class Node {
public:
    int data;
    Node *left, *right;
    Node(int val) {
        data = val;
        left = nullptr;
        right = nullptr;
    }
};


// Function to get height of tree
int getHeight(Node* root, int h) {
    if (root == nullptr)
        return h - 1;
    return max(getHeight(root->left, h + 1), getHeight(root->right, h + 1));
}

// Print Level Order
void levelOrder(Node* root) {
    if (!root) {
        cout << "N
";
        return;
    }

    queue<pair<Node*, int>> q;
    q.push({root, 0});
    int lastLevel = 0;
    int height = getHeight(root, 0);

    while (!q.empty()) {
        auto top = q.front();
        q.pop();
        Node* node = top.first;
        int lvl = top.second;

        if (lvl > lastLevel) {
            cout << "
";
            lastLevel = lvl;
        }

        if (lvl > height)
            break;

       // printing null node
        if (node->data != -1)
            cout << node->data << " ";
        else
            cout << "N ";


          // Null nodes have no children
        if (node->data == -1)
            continue;

        if (node->left == nullptr)
            q.push({new Node(-1), lvl + 1});
        else
            q.push({node->left, lvl + 1});

        if (node->right == nullptr)
            q.push({new Node(-1), lvl + 1});
        else
            q.push({node->right, lvl + 1});
    }
}

//Driver Code Ends


// Recursive Function for inorder traversal
    // to find out the two swapped nodes
void correctBSTUtil(Node* root, Node*& first, Node*& middle,
                                    Node*& last, Node*& prev) {
                                        
    if (root == nullptr)
        return;

    // Recur for left subtree
    correctBSTUtil(root->left, first, middle, last, prev);

    // Detect violation of BST property
    if (prev && root->data < prev->data) {
        // First violation
        if (!first) {
            first = prev;
            middle = root;
        }
        // Second violation
        else {
            last = root;
        }
    }

    // Update previous node
    prev = root;

    // Recur for right subtree
    correctBSTUtil(root->right, first, middle, last, prev);
}

// Function to fix the BST
void correctBST(Node* root) {
    Node *first = nullptr, *middle = nullptr,
                            *last = nullptr, *prev = nullptr;
    correctBSTUtil(root, first, middle, last, prev);
    if (first && last)
        swap(first->data, last->data);
    else if (first && middle)
        swap(first->data, middle->data);
}


//Driver Code Starts

int main() {
    
    //     Constructing the tree with swapped nodes
    //           6
    //         /   \
    //       10     2
    //       / \    / \
    //      1   3  7  12
    
    Node* root = new Node(6);
    root->left = new Node(10);
    root->right = new Node(2);
    root->left->left = new Node(1);
    root->left->right = new Node(3);
    root->right->left = new Node(7);
    root->right->right = new Node(12);

    correctBST(root);
    levelOrder(root);

    return 0;
}

//Driver Code Ends
Java 
//Driver Code Starts
import java.util.LinkedList;
import java.util.Queue;
import java.util.List;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

class Node {
    int data;
    Node left, right;
    Node(int val) {
        data = val;
        left = right = null;
    }
}

class Main {

           // Function to get the height of the tree
    static int getHeight(Node root, int h) {
        if (root == null) return h - 1;
        return Math.max(getHeight(root.left, h + 1), getHeight(root.right, h + 1));
    }

    // Print Level Order
    static void levelOrder(Node root) {
        Queue<List<Object>> queue = new LinkedList<>();
        queue.offer(List.of(root, 0));

        int lastLevel = 0;
        int height = getHeight(root, 0);
        while (!queue.isEmpty()) {
            List<Object> top = queue.poll();

            Node node = (Node) top.get(0);
            int lvl = (int) top.get(1);

            if (lvl > lastLevel) {
                System.out.println();
                lastLevel = lvl;
            }
            if (lvl > height) break;

            // printing null node
            System.out.print((node.data == -1 ? "N" : node.data) + " ");

            // null node has no children
            if (node.data == -1) continue;

            if (node.left == null) queue.offer(List.of(new Node(-1), lvl + 1));
            else queue.offer(List.of(node.left, lvl + 1));

            if (node.right == null) queue.offer(List.of(new Node(-1), lvl + 1));
            else queue.offer(List.of(node.right, lvl + 1));
        }
    }
//Driver Code Ends

    
    static Node first, middle, last, prev;

    // Recursive Function for inorder traversal
    // to find out the two swapped nodes
    static void correctBSTUtil(Node root) {
        if (root == null) return;

        // Recur for the left subtree
        correctBSTUtil(root.left);

        //first violation
       
        if (prev != null && root.data < prev.data) {
            if (first == null) {
                first = prev;
                middle = root;
            }

            //  second violation,
            else {
                last = root;
            }
        }

        // Mark this node as previous
        prev = root;

        // Recur for the right subtree
        correctBSTUtil(root.right);
    }

    // Function to fix the BST
    static void correctBST(Node root) {
        first = middle = last = prev = null;
        correctBSTUtil(root);

        // Fix (or correct) the tree
        if (first != null && last != null)
            swap(first, last);
        else if (first != null && middle != null)
            swap(first, middle);
    }
    static void swap(Node a, Node b) {
        int temp = a.data;
        a.data = b.data;
        b.data = temp;
    }


//Driver Code Starts

    public static void main(String[] args) {

        // Constructing the tree with swapped nodes
        //       6
        //     /  \
        //    10   2
        //   / \  / \
        //  1  3 7  12
        // Here, 10 and 2 are swapped

        Node root = new Node(6);
        root.left = new Node(10);
        root.right = new Node(2);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
        root.right.left = new Node(7);
        root.right.right = new Node(12);

        correctBST(root);
        levelOrder(root);
    }
}

//Driver Code Ends
Python 
#Driver Code Starts

class Node:
    def __init__(self, val):
        self.data = val
        self.left = None
        self.right = None

# Function to get the height of the tree
def getHeight(root, h):
    if root is None:
        return h - 1
    return max(getHeight(root.left, h + 1), getHeight(root.right, h + 1))


# Print level Order
def levelOrder(root):
    from collections import deque
    queue = deque()
    queue.append((root, 0))

    lastLevel = 0

    height = getHeight(root, 0)

    while queue:
        node, lvl = queue.popleft()

        if lvl > lastLevel:
            print()
            lastLevel = lvl

        if lvl > height:
            break

        # printing null node
        print("N" if node.data == -1 else node.data, end=" ")

        # null node has no children
        if node.data == -1:
            continue

        if node.left is None:
            queue.append((Node(-1), lvl + 1))
        else:
            queue.append((node.left, lvl + 1))

        if node.right is None:
            queue.append((Node(-1), lvl + 1))
        else:
            queue.append((node.right, lvl + 1))

#Driver Code Ends


# Global pointers
first = None
middle = None
last = None
prev = None


# Recursive Function for inorder traversal
# to find out the two swapped nodes
def correctBSTUtil(root):
    global first, middle, last, prev
    if root is None:
        return

    # Recur for the left subtree
    correctBSTUtil(root.left)

    if prev and root.data < prev.data:

        # first violation
        if first is None:
            first = prev
            middle = root

        # second violation
        else:
            last = root

    # Mark this node as previous
    prev = root

    # Recur for the right subtree
    correctBSTUtil(root.right)


# Function to fix the given BST
def correctBST(root):
    global first, middle, last, prev
    first = middle = last = prev = None

    correctBSTUtil(root)
    if first and last:
        swap(first, last)
    elif first and middle:
        swap(first, middle)

def swap(a, b):
    temp = a.data
    a.data = b.data
    b.data = temp


#Driver Code Starts


if __name__ == "__main__":
    
    # Constructing the tree with swapped nodes
    #       6
    #     /  \
    #    10   2
    #   / \  / \
    #  1  3 7  12
 

    root = Node(6)
    root.left = Node(10)
    root.right = Node(2)
    root.left.left = Node(1)
    root.left.right = Node(3)
    root.right.left = Node(7)
    root.right.right = Node(12)

    correctBST(root)
    levelOrder(root)

#Driver Code Ends
C# 
//Driver Code Starts
using System;
using System.Collections.Generic;

class Node {
    public int data;
    public Node left, right;
    public Node(int val) {
        data = val;
        left = right = null;
    }
}

class Solution {
    
        // Function to get the height of the tree
    static int getHeight(Node root, int h) {
        if (root == null) return h - 1;
        return Math.Max(getHeight(root.left, h + 1), getHeight(root.right, h + 1));
    }

    // Print Level Order
    static void levelOrder(Node root) {
        if (root == null) return;

        Queue<(Node, int)> queue = new Queue<(Node, int)>();
        queue.Enqueue((root, 0));

        int lastLevel = 0;
        int height = getHeight(root, 0);

        while (queue.Count > 0) {
            var (node, lvl) = queue.Dequeue();

            if (lvl > lastLevel) {
                Console.WriteLine();
                lastLevel = lvl;
            }
            if (lvl > height) break;

            // printing null node
            Console.Write((node.data == -1 ? "N" : node.data.ToString()) + " ");

            // null node has no children
            if (node.data == -1) continue;

            if (node.left == null) queue.Enqueue((new Node(-1), lvl + 1));
            else queue.Enqueue((node.left, lvl + 1));

            if (node.right == null) queue.Enqueue((new Node(-1), lvl + 1));
            else queue.Enqueue((node.right, lvl + 1));
        }
    }
//Driver Code Ends

    
    static Node first = null, middle = null, last = null, prev = null;

    // Recursive Function for inorder traversal
    // to find out the two swapped nodes
    static void correctBSTUtil(Node root) {
        if (root == null) return;
        correctBSTUtil(root.left);
        if (prev != null && root.data < prev.data) {

            //  first violation
            if (first == null) {
                first = prev;
                middle = root;
            }
            //  second violation,
            else {
                last = root;
            }
        }

        // Mark this node as previous
        prev = root;

        // Recur for the right subtree
        correctBSTUtil(root.right);
    }

    // Function to fix the given BST
    static void correctBST(Node root) {
        first = middle = last = prev = null;
        correctBSTUtil(root);
        if (first != null && last != null)
            Swap(first, last);
        else if (first != null && middle != null)
            Swap(first, middle);
    }

    static void Swap(Node a, Node b) {
        int temp = a.data;
        a.data = b.data;
        b.data = temp;
    }



//Driver Code Starts
    static void Main() {
        
    //      Constructing the tree with swapped nodes
    //       6
    //      /  \
    //     10   2
    //    / \  / \
    //   1  3 7  12
        
        
        Node root = new Node(6);
        root.left = new Node(10);
        root.right = new Node(2);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
        root.right.left = new Node(7);
        root.right.right = new Node(12);

        correctBST(root);
        levelOrder(root);
    }
}

//Driver Code Ends
JavaScript 
//Driver Code Starts
class Node {
    constructor(val) {
        this.data = val;
        this.left = null;
        this.right = null;
    }
}

// Queue implementation for Node*
class QNode {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class Queue {
    constructor() {
        this.front = null;
        this.rear = null;
    }

    isEmpty() {
        return this.front === null;
    }

    enqueue(x) {
        let newNode = new QNode(x);
        if (this.rear === null) {
            this.front = this.rear = newNode;
            return;
        }
        this.rear.next = newNode;
        this.rear = newNode;
    }

    dequeue() {
        if (this.front === null)
            return null;

        let temp = this.front;
        this.front = this.front.next;

        if (this.front === null)
            this.rear = null;

        return temp.data;
    }
}

// Function to get the height of the tree
function getHeight(root, h) {
    if (root === null) return h - 1;
    return Math.max(getHeight(root.left, h + 1), 
                           getHeight(root.right, h + 1));
}

// Print Level Order
function levelOrder(root) {
    let queue = [];
    queue.push([root, 0]);

    let lastLevel = 0;
    let height = getHeight(root, 0);

    while (queue.length > 0) {
        let [node, lvl] = queue.shift();

        if (lvl > lastLevel) {
            console.log("");
            lastLevel = lvl;
        }
        if (lvl > height) break;

        // printing null node
        process.stdout.write((node.data === -1 ? "N" : node.data) + " ");

        // null node has no children
        if (node.data === -1) continue;

        if (node.left === null) 
        queue.push([new Node(-1), lvl + 1]);
        else 
        queue.push([node.left, lvl + 1]);

        if (node.right === null)
        queue.push([new Node(-1), lvl + 1]);
        else 
        queue.push([node.right, lvl + 1]);
    }
}

//Driver Code Ends

// Global pointers
let first = null, middle = null, last = null, prev = null;

// Recursive Function for inorder traversal
// to find out the two swapped nodes
function correctBSTUtil(root) {
    if (root === null) return;

    // Recur for the left subtree
    correctBSTUtil(root.left);

    // If this node is smaller than the previous node,
    // it's violating the BST rule
    if (prev !== null && root.data < prev.data) {

        //first violation
        if (first === null) {
            first = prev;
            middle = root;
        }
        // second violation
        else {
            last = root;
        }
    }

    // Mark this node as previous
    prev = root;

    // Recur for the right subtree
    correctBSTUtil(root.right);
}

// Function to fix the given BST
function correctBST(root) {
    first = middle = last = prev = null;
    correctBSTUtil(root);
    if (first !== null && last !== null)
        swap(first, last);
    else if (first !== null && middle !== null)
        swap(first, middle);
}

// Utility function to swap values of two nodes
function swap(a, b) {
    let temp = a.data;
    a.data = b.data;
    b.data = temp;
}


//Driver Code Starts

// Driver code

    //      Constructing the tree with swapped nodes
    //        6
    //      /  \
    //     10   2
    //    / \  / \
    //   1  3 7  12
let root = new Node(6);
root.left = new Node(10);
root.right = new Node(2);
root.left.left = new Node(1);
root.left.right = new Node(3);
root.right.left = new Node(7);
root.right.right = new Node(12);

correctBST(root);
levelOrder(root);


//Driver Code Ends

Output
6 
2 10 
1 3 7 12
Comment

Explore