Two nodes of a BST are swapped, correct the BST

Approach

The Brute Force approach to this problem can be to perform any traversal, say inorder. 

Store that traversal in an auxiliary array and sort it. 

Make an inorder tree out of that sorted auxiliary array. You will get the correct Binary Search Tree.

The issue here is that the complexities of this approach are not optimum. The time complexity will be O(n log n), which is not acceptable. Also, we are using an extra stack to store the auxiliary array, which can be avoided if we choose the optimum approach given below. It does not affect the space complexity because auxiliary space is a kind of temporary storage. Still, it occupies extra space which can be avoided.

Optimum Approach

Firstly, we will perform an inorder traversal for the incorrect tree in which two swapped nodes are present. Observe the traversal. There can be only two cases.

🍄 Swapped Nodes are not adjacent to each other.

While performing the inorder traversal, see if every element is greater than the previous element. Find those two elements that are less than the previous element. There will be two violations. Swap those two elements, and your work is done.

🍄 Swapped Nodes are adjacent to each other.

In this case, there will be only one violation. Again, while performing the inorder traversal, see if every element is greater than the previous element. Find those two elements that are less than the previous element. Till here, you might have observed that the process is similar. The only difference is that here you need to store the previous element and the one violating. You will get only one pair. Swap the elements, and your work is done.

Algorithm

We know that there can be two cases to solve this problem. We will discuss the algorithms for both, one after another.

🥀 Swapped Nodes are not adjacent to each other.

1. Move from left to right in the inorder traversal.
2. When you find a node whose value is lesser than the value of the previous node, save the content of the previous node.
3. Again proceed to the right.
4. When you find another node whose value is less than the previous node, save the node’s content.
5. Swap the contents of the two nodes saved in the previous steps.

🥀 Swapped Nodes are adjacent to each other.

1. Make three-pointers, start, mid, and end.
2. Move from left to right in the inorder traversal.
3. When you find a node whose value is lesser than the value of the previous node, update start to point to the previous node, update mid to point to the current node.
4. Keep moving to the right again.
5. When a node is found whose value is less than the value of the previous node, update the value of the end to point to this node.
6. If the end is null, swap start and mid. Else, swap start and end.

Implementation in Java

// Java program to fix the BST 
import java.util.*;
import java.lang.*;
import java.io.*;
  
class TreeNode {
    int value;
    TreeNode l, r;
    TreeNode(int data)
    {
        value = data;
        l = r = null;
    }
}
  
class Main
{
    TreeNode start, mid, end, previous;
    public static void main (String[] args) 
    {
        //Incorrect BST
        TreeNode parent = new TreeNode(25);
        parent.l = new TreeNode(30);
        parent.r = new TreeNode(17);
        parent.l.l = new TreeNode(13);
        parent.l.r = new TreeNode(19);
        parent.r.r = new TreeNode(27);
        parent.r.l = new TreeNode(33);
  
        System.out.println("Original Tree");
        Main tree = new Main();
        tree.Inorder(parent);
        tree.printBST(parent);
        System.out.println();
        System.out.println("Fixed Tree");
        tree.Inorder(parent);
    }
     //function to correct the BST
    void fixBST(TreeNode parent)
    {
        if(parent != null)
        {
            fixBST(parent.l);
  
            if (previous != null && parent.value < previous.value)
            {
                if (start == null)
                {
                    start = previous;
                    mid = parent;
                }
                else
                    end = parent;
            }
            previous = parent;
            fixBST(parent.r);
        }
    }
    //function to print the correct BST
    void printBST(TreeNode root)
    {
        start = mid = end = previous = null;
        fixBST(root);
        if(start != null && end != null)
        {
            int temp = start.value;
            start.value = end.value;
            end.value = temp; 
        }
        else if(start != null && mid != null) 
        {
            int temp = start.value;
            start.value = mid.value;
            mid.value = temp;
        }
    }
     //function to get inorder of given BST
    void Inorder(TreeNode node)
    {
        if (node == null)
            return;
        Inorder(node.l);
        System.out.print(" " + node.value);
        Inorder(node.r);
    }
}

Input:

13 30 19 25 33 17 27

Output: 

Original Tree
13 30 19 25 33 17 27
Fixed Tree
13 17 19 25 33 17 30

Complexity Analysis
 

🥝 Time Complexity: O(n) 
In the implementation above, the pointer may have to traverse all the nodes to get the inorder traversal. Therefore, in this case, the time complexity will be O(n).

🥝 Space Complexity: O(1)
Since we are not using any extra space to compute our answer, therefore, the space complexity would be O(1).

Check out this problem - Connect Nodes At Same Level

Frequently Asked Questions

What are some basic operations that can be performed in a BST?

A Binary Search Tree is like any other tree. Thus, every operation that can be performed in a casual tree, can also be performed in a Binary Search Tree. These operations are Searching, Insertion, Preorder Traversal, Inorder Traversal, and Postorder Traversal.

How to define a node of a BST?

You can use the following code snippet to define a node of a BST.

example node {
   int data;   
   example node *leftChild;
   example node *rightChild;
};

Mention the properties of BST that differentiate it from a normal Binary Tree.

A Binary Tree is a tree that does not contain more than two child nodes. It is not compulsory that all the nodes of its left subtree must be smaller than the root node, nor it is necessary for all the nodes of its right subtree to be greater. But, in a Binary Search Tree, these are some mandatory properties to be followed by every node of that tree.

Conclusion

To summarize the article, we looked at the problem statement, looked at every possible condition that could occur, understood the approach, went through the Pseudocode, saw the implementation, tested the code against an example output, and did time and space complexities analysis.

We hope the above discussion helped you understand and solve the problem better.

This will also help you learn how to approach any problem like this in the future.

For coders who want to solve more such questions, refer to the list below.

• Partial BST
• Distinct Subsequences
• kth smallest node in BST
• Count Unique BSTs

Enroll in our courses, go for mock tests, solve problems available, and interview puzzles. Also, you can focus on interview stuff- interview experiences and an interview bundle for placement preparations. Do upvote our blog to help other ninjas grow.

Happy Coding!