Fix BST
Given a Binary Search Tree, where exactly two nodes of the same tree were swapped by mistake. The task is to restore or fix the BST, without changing its structure.

A binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree.

Note:

Given BST will not contain duplicates.

A Binary Search Tree (BST) whose 2 nodes have been swapped is shown below.

After swapping the incorrect nodes:

Follow Up

Can you do this without using any extra space?

Input Format

The first line of input contains an integer T, the number of test cases. The first line of every test case contains elements in the level order form. The input consists of values of nodes separated by a single space in a single line. In case a node is null, we take -1 on its place. For example, the input for the tree depicted in the above image would be: { 20 30 35 5 15 10 42 -1 -1 13 -1 -1 -1 -1 -1 -1 -1 }

Explanation :

Level 1 : The root node of the tree is 20 Level 2 : Left child of 20 = 30 Right child of 20 = 35 Level 3 : Left child of 30 = 5 Right child of 30 = 15 Left child of 35 = 10 Right child of 35 = 42 Level 4 : Left child of 5 = null (-1) Right child of 5 = null (-1) Left child of 15 = 13 Right child of 15 = null (-1) Left child of 30 = null (-1) Right child of 30 = null (-1) Left child of 42 = null (-1) Right child of 42 = null (-1) Level 5: Left child of 13 = null (-1) Right child of 13 = null (-1) The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on. The input ends when all nodes at the last level are null (-1).

Note :

The above format was just to provide clarity on how the input is formed for a given tree. The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the level order will be given as: 20 30 35 5 15 10 42 -1 -1 13 -1 -1 -1 -1 -1 -1 -1

Output Format:

For every test case, print the level order traversal of the restored tree. The output of each test case is printed in a separate line.

Note:

You don’t have to print anything, it has already been taken care of. Just implement the function.

Constraints:

1

Question

Fix BST

Given a Binary Search Tree, where exactly two nodes of the same tree were swapped by mistake. The task is to restore or fix the BST, without changing its structure.

A binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree.

Note:

Given BST will not contain duplicates.

A Binary Search Tree (BST) whose 2 nodes have been swapped is shown below.

example

After swapping the incorrect nodes:

example

Follow Up

Can you do this without using any extra space?

Input Format

The first line of input contains an integer T, the number of test cases.

The first line of every test case contains elements in the level order form. The input consists of values of nodes separated by a single space in a single line. In case a node is null, we take -1 on its place.

For example, the input for the tree depicted in the above image would be: { 20 30 35 5 15 10 42 -1 -1 13 -1 -1 -1 -1 -1 -1 -1 }

Explanation :

Level 1 :
The root node of the tree is 20

Level 2 :
Left child of 20 = 30
Right child of 20 = 35

Level 3 :
Left child of 30 = 5
Right child of 30 = 15
Left child of 35 = 10
Right child of 35 = 42

Level 4 :
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 15 = 13
Right child of 15 = null (-1)
Left child of 30 = null (-1)
Right child of 30 = null (-1)
Left child of 42 = null (-1)
Right child of 42 = null (-1)

Level 5:
Left child of 13 = null (-1)
Right child of 13 = null (-1) 

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are null (-1).

Note :

The above format was just to provide clarity on how the input is formed for a given tree. 
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the level order will be given as:
20 30 35 5 15 10 42 -1 -1 13 -1 -1 -1 -1 -1 -1 -1

Output Format:

For every test case, print the level order traversal of the restored tree.
The output of each test case is printed in a separate line.

Note:

You don’t have to print anything, it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 100    
1 <= N <= 10^3
0 <= data <= 10^9

Where ‘data’ denotes the value of the nodes in the given tree.

Time limit: 1 second

Accepted Answer

After getting some of the hints, was able to come up with in-order traversal approach which takes extra space. Interviewer wanted better approach without extra space. But couldn't think of it.

Accepted Answer

Sorting based Approach

The steps are as follows:

Maintain an array, say ‘INORDERTRAVERSAL’, and store the inorder traversal of the given BST in this array.
Now sort the ‘INORDERTRAVERSAL’ array.
After sorting, we have the valid BST’s inorder traversal.
Again, traverse the tree in inorder fashion and keep updating the value at each node according to the ‘inOrderTraversal’ array.

Algorithm for storing inorder traversal :

void inorder('ROOT', ‘INORDERTRAVERSAL’)

Until all the nodes are traversed
- Recursively traverse the left subtree.
- Add the current node’s value to the ‘INORDERTRAVERSAL’ array.
- Recursively traverse the right subtree.

Space Complexity: O(1)Explanation:

O(N), where ‘N’ is the number of nodes of the given BST.

Since we are storing the value of every node of the tree in the array. Thus, the final space complexity is O(N).

Time Complexity: O(1)Explanation:

O(N * log(N)) where ‘N’ is the number of nodes in the given BST.

Since we are traversing the tree for storing the inorder traversal and then we are sorting the array. Storing in order traversal and the final process of updating the values of the nodes can be done in O(N) time. Sorting the array takes O(N * log(N)) time and thus, the final time complexity is O(N + N * log(N) + N) = O(N * log(N)).

Accepted Answer

InOrder Traversal Approach

The steps are as follows:

Maintain an array, say ‘INORDERTRAVERSAL’, and store the inorder traversal of the given BST in this array.
Traverse the array from left to right and find these two out-of-order values and swap them.
After swapping, we have the valid BST’s inorder traversal.
Again, traverse the tree in an inorder fashion and keep updating the value at each node according to the ‘INORDERTRAVERSAL’ array.

For example:

Consider, ‘INORDERTRAVERSAL’ = { 10, 50, 30, 40, 20, 60 }.

For a valid BST, this ‘INORDERTRAVERSAL’ should be sorted in ascending order.

We can see that 50 is larger than 30 and it should come after 30. So, 50 is our first incorrect node.

When we found our first incorrect node, we will keep traversing the array and find the first node which is less than 30, because it should come at the place of 50.

We can see, 20 is our second incorrect node.

Now we will swap 50 and 20.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes of the given BST.

Since we are storing the value of every node of the tree in the array. Thus, the final space complexity is O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes in the given BST.

Since we are traversing the tree for storing the inorder traversal and then we are traversing the array. Storing in order traversal and the final process of updating the values of the nodes can be done in O(N) time. Finding two out-of-order nodes and swapping them also takes O(N) time and thus, the final time complexity is O(N + N + N) = O(N).

Accepted Answer

Recursion

The idea is to visit the tree in an in-order fashion and search for two swapped nodes. After finding the incorrect nodes, we will swap their data.

The steps are as follows:

1. We will maintain a ‘PREV’ node to keep track of the previous node of the current node ‘CURR’.

2. We will also maintain ‘FIRST’ and ‘SECOND’ nodes to store the swapped or incorrect nodes.

3. Initialise three nodes, ‘PREV’, ‘FIRST’, and ‘SECOND’ by NULL.

4. We will use a recursive function that takes the root of the BST, ‘PREV’, ‘FIRST’, and ‘SECOND’ as arguments.

5. We will find the incorrect pair by comparing the value of the ‘PREV’ node with the value of the ‘CURR’ node.

Note: For a valid BST, the value of the previous node should always be smaller than the value of the current node in the inorder traversal.

6. When the value of the ‘prev’ node is greater than the value of the ‘CURR’ node, it means that we have found an incorrect node. Here, we have two cases :

If it is the first time we found an incorrect pair, the ‘PREV’ node must be the ‘FIRST’ incorrect node.
If it is not the first time we found an incorrect pair, the ‘CURR’ node must be the ‘SECOND’ incorrect node.

7. We will store these nodes and swap the value of these incorrect nodes to recover the BST.

Space Complexity: O(n)Explanation:

O(N), Where ‘N’ is the number of nodes in the BST.

Since a recursion stack of size O(H) is required while traversing the tree in an inorder fashion. In the worst case, the height of the tree will be the total number of nodes in the BST i.e ‘N’. Thus, the final space complexity is O(N).

Time Complexity: O(n)Explanation:

O(N), Where ‘N’ is the number of nodes in the BST.

Since we are visiting each node in the tree exactly once which requires O(N) time. Thus the time complexity will be O(N).

Accepted Answer

Morris Traversal

The idea is to visit the tree in an inorder fashion and search for two swapped nodes. After finding the incorrect nodes, we will swap their data.

This approach is very similar to the previous approach but here we will not use recursion or any extra data structure to store the nodes. We will be using Morris Traversal.

In inorder traversal, first, we visit the left subtree, then the root node, and the right subtree. As we are not using recursion or stack, we will be creating a back-link between a node and its inorder successor.

Morris traversal is similar to recursive/iterative traversal, but we need to modify the tree structure during the traversal. Before visiting the left tree of a root, we will build a back-link between the rightmost node in the left tree and the root. So, we can go back to the root node when we are done with the left tree. Then we locate the rightmost node in the left subtree again, cut the back-link, recover the tree structure and start visiting the right subtree.

For example: In the picture below, back-links between (4-2) and (5-1) are created.

When we are done visiting 4, we can go to the next node of 4 in its inorder traversal (in order successor) using this back-link.
When we are done visiting 5, we can go to the next node of 5 in its inorder traversal (in order successor) using this back-link.

For a detailed explanation of Morris's traversal, click here.

Note: For a valid BST, the value of the previous node should always be smaller than the value of the current node in the inorder traversal.

The steps are as follows:

1. Initialise a current node ‘CURR’ by the root node.

2. Maintain a ‘PREV’ node to keep track of the previous node of the current node ‘CURR’.

3. We will also maintain ‘FIRST’ and ‘SECOND’ nodes to store the incorrect nodes.

4. Initialise ‘PREV’, ‘FIRST’, and ‘SECOND’ by NULL.

5. While ‘CURR’ is not NULL:

We check if ‘CURR’ has a left child.
- If it does not have a left child, we check if the ‘PREV’ node and the ‘CURR’ node form an incorrect pair. When the value of the ‘PREV’ node is greater than the value of the ‘CURR’ node, they form an incorrect pair. Here, we have two cases :
If it is the first time we found an incorrect pair, the ‘PREV’ node must be the ‘FIRST’ incorrect node.
If it is not the first time we found an incorrect pair, the ‘CURR’ node must be the ‘SECOND’ incorrect node. If it has a left child, we first create the back-link from the rightmost node in the left subtree and ‘CURR’. Then, we check if ‘CURR’ and ‘PREV’ form an incorrect pair. When the value of the ‘PREV’ node is greater than the value of the ‘CURR’ node, they form an incorrect pair. Here, we have two cases :
- If it is the first time we found an incorrect pair, the ‘PREV’ node must be the ‘FIRST’ incorrect node.
- If it is not the first time we found an incorrect pair, the ‘CURR’ node must be the ‘SECOND’ incorrect node.
Keep updating the ‘prev’ and the ‘CURR’ node.

6. Now, we will swap the value of these ‘FIRST’ and the ‘SECOND’ nodes to recover the BST.

Space Complexity: O(1)Explanation:

O(1)

Since we are not using any extra data structure. Only constant additional space is required. Thus the space complexity will be O(1).

Time Complexity: O(n)Explanation:

O(N), where N is the number of nodes in the BST.

Since we are visiting each node in the tree exactly once which requires O(N) time. Thus the time complexity will be O(N).

Given a Binary Search Tree, where exactly two nodes of the same tree were swapped by mistake. The task is to restore or fix the BST, without changing its structure.

A binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree.

Note:

A Binary Search Tree (BST) whose 2 nodes have been swapped is shown below.

After swapping the incorrect nodes:

Follow Up

Input Format

Explanation :

Note :

Output Format:

Note:

Constraints:

Top Oyo Rooms Software Developer interview questions & answers

Popular interview questions of Software Developer