## 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: **

Input Binary Search Tree: Output Binary Search Tree: |

**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:**

Input Binary Search Tree: Output Binary Search Tree: |

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