Binary Tree to BST Transformation Task
Given a binary tree consisting of 'N' nodes with distinct integer values, transform it into a Binary Search Tree (BST) while maintaining the original structure of the binary tree.
Explanation:
The transformation should maintain the shape of the original binary tree. A Binary Search Tree (BST) adheres to the following rules:
• Nodes in the left subtree hold values less than the node's value.
• Nodes in the right subtree hold values greater than the node's value.
• Both subtrees must themselves be binary search trees.
Input:
The first line contains an integer 'T' representing the number of test cases.
Each test case is described as a single line containing space-separated integers representing the binary tree's level order traversal.
If a node is absent, '-1' is used in its place.
Output:
For each test case, return the level order traversal of the transformed BST as a single line.
Example:
Given Binary Tree:
Diagram depicting the input binary tree structure
Resulting BST:
Diagram depicting the resulting BST structure
Constraints:
1 ≤ T ≤ 10^2
1 ≤ N ≤ 5 * 10^3
0 ≤ data ≤ 10^5
anddata ≠ -1
Time Limit: 1 sec
Note:
No output function is required; focus on implementing the transformation function.
AnswerBot
3d
Transform a binary tree into a Binary Search Tree (BST) while maintaining the original structure.
Implement a function to transform the binary tree into a BST by rearranging the nodes based on BST rule...read more
Help your peers!
Add answer anonymously...
Popular interview questions of Software Developer
>
Collegedunia Software Developer Interview Questions
Stay ahead in your career. Get AmbitionBox app
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+
Reviews
4 L+
Interviews
4 Cr+
Salaries
1 Cr+
Users/Month
Contribute to help millions
Get AmbitionBox app