
Asked in Samsung
BST to Greater Tree Conversion
Convert a given binary search tree (BST) with 'N' nodes into a Greater Tree. In this transformation, each node's data is modified to the sum of the original node's data plus the sum of all nodes' data that are greater than or equal to the original node's data within the BST.
Input:
The first line contains an integer 'T' representing the number of test cases.
For each test case, the subsequent line contains the tree elements in level order, separated by a space. Use -1 to denote missing nodes.
Output:
For each test case, output a single integer on a new line, representing the root node of the modified Greater Tree.
Example:
Given the input for level order traversal as:
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
Output will be the root node after converting the BST.

Constraints:
1 <= T <= 100
0 <= N <= 3000
-10^6 <= DATA <= 10^6
- Duplicate elements can be present, placed in either left or right subtrees.
- Time Limit: 1 sec
Note:
You do not have to manage input/output operations. Implement the function to modify the BST.

AnswerBot
4mo
Convert a given BST into a Greater Tree by updating each node's data to the sum of original data and all greater nodes' data.
Traverse the BST in reverse inorder (right, root, left) to update each node...read more
Help your peers!
Add answer anonymously...
Top Software Developer Intern Interview Questions Asked at Samsung
Q. Suppose an array of length n sorted in ascending order is rotated between 1 and ...read more
Q. What are the ACID properties in DBMS?
Q. Sum of Digits Problem Statement Given an integer 'N', continue summing its digit...read more
Interview Questions Asked to Software Developer Intern at Other Companies
Top Skill-Based Questions for Samsung Software Developer Intern
C++ Interview Questions and Answers
300 Questions
Algorithms Interview Questions and Answers
250 Questions
Data Structures Interview Questions and Answers
250 Questions
Web Development Interview Questions and Answers
250 Questions
Operating Systems Interview Questions and Answers
250 Questions
System Design Interview Questions and Answers
250 Questions
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

