1.
Introduction
2.
Problem Statement
2.1.
Sample Examples
3.
Approach
4.
Optimum Approach
4.1.
Algorithm
4.2.
Implementation in Java
4.2.1.
Complexity Analysis
5.
5.1.
What are some basic operations that can be performed in a BST?
5.2.
How to define a node of a BST?
5.3.
Mention the properties of BST that differentiate it from a normal Binary Tree.
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Two nodes of a BST are swapped, correct the BST

Rupal Saluja
0 upvote

## Introduction

In this blog, we will understand a very interesting problem of a Binary Search Tree data structure. In this problem, we will learn how to correct the BST. Swapping two nodes has disturbed the BST, so what can be done to recover the BST?

Thus, through this problem, we will learn the approach to swapping the nodes of a Binary Search Tree and correcting it in case of disturbances. Firstly, we will examine the problem statement, learn about the Binary Search tree data structure, and decide on the optimum approach. Then we will proceed toward the implementation in the programming languages.

Binary Search Tree

A Binary Search Tree is a type of Binary tree data structure. A Binary Tree is one in which elements have the utmost two children nodes. Since elements in this data structure have only two child nodes, we name them the left child and the right child. Any node of Binary contains the following information. These are its data and pointers to its left and right child.

For Example, if we consider the tree below, 35 is the root node, and the rest of the nodes are its children nodes. We pick any node, say 20, so 18 will be its left child, and 22 will be its right child. 20 is the parent node to child nodes 18 and 22.

Three properties of a Binary Search Tree differentiate it from a normal Binary Tree. These properties are mentioned below in the list.

• The left subtree of any node will contain only those nodes whose value is lesser than that node’s value.
• The right subtree of any node will contain only those nodes whose value is greater than that node’s value.
• All the subtrees must also be binary search trees.

## Problem Statement

We are given a binary search tree that has n nodes. We have to correct the BST that has been disturbed due to swapping its nodes. When we say fixing the BST, we mean that each node must follow all three properties of a BST mentioned above.

Here, we assume that all the nodes’ values are positive. Let us understand this with the help of an example.

Suppose that we have a binary search tree, as seen in the image below. We have to search for floor and ceil in a Binary Search Tree. We will use the same binary search tree for different examples to grab all the possible cases better.

### Sample Examples

🌴 Example 1:

Explanation

In the example above, we can see two trees, one in which two nodes are incorrect and the one in which swapping has been done to correct the BST. When you observe the input tree, you will find that node ‘40’ in the left subtree is greater than its root value. Also, node ‘19’ present in the right subtree is smaller than the root node. These have caused a disturbance in the tree as it does not follow the properties of BST now. We got two nodes that will be swapped to correct the tree.

In the tree next, we see that the two nodes are present in a position following the properties of a BST. Hence, we can say that we have fixed the BST.

🌴 Example 2:

Explanation

We will see one more example to get a clearer picture. Again, in the example above, we can see two trees, one in which two nodes are incorrect and one in which swapping has been done to correct the BST. When you observe the input tree, you will find that node ‘32’ present in the left subtree is greater than its root value. Also, node ‘19’ in the right subtree is smaller than the root node. These have caused disturbance in the tree as it does not follow the properties of BST now. We got two nodes that will be swapped to correct the tree.

In the tree next, we see that the two nodes are present in a position following the properties of a BST. Hence, we can say that we have fixed 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

### 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.

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!

Live masterclass