Fixing a Swapped Binary Search Tree
Given a Binary Search Tree (BST) where two nodes have been swapped by mistake, your task is to restore or fix the BST without changing its structure.
Input:
The first line of input contains an integer T, representing the number of test cases.
The first line of each test case contains the elements of the tree in level order form, separated by spaces in a single line. The value -1 denotes a null node.
Output:
For each test case, output the level order traversal of the restored tree in a separate line.
Example:
Input:
1
20 30 35 5 15 10 42 -1 -1 13 -1 -1 -1 -1 -1 -1 -1
Output:
20 5 35 30 15 10 42 13
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
Note:
The BST will not contain duplicate nodes. The input format description provides clarity on how level order input is structured. No extra space other than the recursion stack should be used to solve this problem.

AnswerBot
4mo
Restore a Binary Search Tree by fixing two swapped nodes without changing its structure.
Identify the two swapped nodes by performing an inorder traversal of the BST.
Swap the values of the two identifi...read more
Help your peers!
Add answer anonymously...
Housing.com Software Engineer interview questions & answers
A Software Engineer was asked Q. Implement a find functionality (similar to Ctrl+F) in a file. What data structur...read more
A Software Engineer was asked Q. Create a set of all nodes that can occur in any path from a source to a destinat...read more
A Software Engineer was asked Q. Given two sides of a river having the same cities labeled in characters, find th...read more
Popular interview questions of Software Engineer
A Software Engineer was asked Q1. Implement a find functionality (similar to Ctrl+F) in a file. What data structur...read more
A Software Engineer was asked Q2. Create a set of all nodes that can occur in any path from a source to a destinat...read more
A Software Engineer was asked Q3. Given two sides of a river having the same cities labeled in characters, find th...read more
Stay ahead in your career. Get AmbitionBox app


Trusted by over 1.5 Crore job seekers to find their right fit company
80 L+
Reviews
10L+
Interviews
4 Cr+
Salaries
1.5 Cr+
Users
Contribute to help millions
AmbitionBox Awards
Get AmbitionBox app

