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 and data ≠ -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...
Collegedunia Software Developer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
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

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter