Log inSign up
mediumLeetCodeNot Started

Convert BST to Greater Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on LeetCode
Lesson

Problem Statement

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.

Recall that a binary search tree satisfies: - The left subtree of a node contains only nodes with keys less than the node's key. - The right subtree of a node contains only nodes with keys greater than the node's key. - Both the left and right subtrees must also be binary search trees.

Constraints:

  • The number of nodes in the tree is in the range [0, 104].
  • -104 <= Node.val <= 104
  • All the values in the tree are unique.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the Reverse Inorder Traversal pattern (Right -> Node -> Left).
  • Accumulate running suffix sums directly across tree pointers.
  • Implement the O(1) auxiliary space Reverse Morris Traversal.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Add all greater elements to current node in BST.
  • Reverse sorted order accumulation.
  • In-place tree value transformation.

Algorithmic Decision Tree:

  • Traverse Right child first, process Root, traverse Left child last.
  • Maintain global running sum.

Connected Patterns:

Binary Tree Inorder TraversalRecover Binary Search TreeMorris Traversal

1. Two-Pass Inorder with Suffix Array

Intuition

Pass 1: Collect all nodes in a list using standard inorder traversal. Pass 2: Calculate suffix sums backwards. Pass 3: Overwrite each node's value with its corresponding suffix sum.

When to apply: Basic baseline before realizing the running sum can be maintained on-the-fly.

Algorithm

  1. Step 1: Traverse inorder, appending nodes to a list.
  2. Step 2: Compute running sum from right to left.
  3. Step 3: Assign nodes[i].val = runningSum.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5struct TreeNode {
6 int val;
7 TreeNode *left, *right;
8 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9};
10
11class Solution {
12 void inorder(TreeNode* node, vector<TreeNode*>& nodes) {
13 if (!node) return;
14 inorder(node->left, nodes);
15 nodes.push_back(node);
16 inorder(node->right, nodes);
17 }
18public:
19 TreeNode* convertBST(TreeNode* root) {
20 vector<TreeNode*> nodes;
21 inorder(root, nodes);
22 int sum = 0;
23 for (int i = (int)nodes.size() - 1; i >= 0; i--) {
24 sum += nodes[i]->val;
25 nodes[i]->val = sum;
26 }
27 return root;
28 }
29};
30
31int main() {
32 TreeNode* root = new TreeNode(4);
33 root->left = new TreeNode(1);
34 root->right = new TreeNode(6);
35 Solution sol;
36 sol.convertBST(root);
37 cout << "Root: " << root->val << ", Left: " << root->left->val << ", Right: " << root->right->val << endl;
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(N)

2. Reverse Inorder DFS (Right -> Root -> Left)

Intuition

Maintain a running variable sum = 0. Recursively explore root.right first, add root.val to sum, update root.val = sum, and then recursively explore root.left. This performs the entire transformation in a single pass without storing nodes.

When to apply: The standard clean recursive solution in interviews.

Algorithm

  1. Step 1: Initialize global/accumulator sum = 0.
  2. Step 2: Helper dfs(node): if node == null, return.
  3. Step 3: dfs(node.right).
  4. Step 4: sum += node.val; node.val = sum;.
  5. Step 5: dfs(node.left).
  6. Step 6: Return root.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode *left, *right;
7 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11 int sum = 0;
12 void dfs(TreeNode* node) {
13 if (!node) return;
14 dfs(node->right);
15 sum += node->val;
16 node->val = sum;
17 dfs(node->left);
18 }
19public:
20 TreeNode* convertBST(TreeNode* root) {
21 sum = 0;
22 dfs(root);
23 return root;
24 }
25};
26
27int main() {
28 TreeNode* root = new TreeNode(4);
29 root->left = new TreeNode(1);
30 root->right = new TreeNode(6);
31 Solution sol;
32 sol.convertBST(root);
33 cout << "Optimal Root: " << root->val << ", Left: " << root->left->val << ", Right: " << root->right->val << endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(H) recursion stack

3. Reverse Morris Traversal (O(1) Auxiliary Space)

Intuition

Reverse Morris Traversal links the leftmost node in the right subtree back to the current node as a temporary predecessor thread. It visits nodes in Right -> Root -> Left order using O(1) extra space.

When to apply: When strict O(1) auxiliary space is required.

Algorithm

  1. Step 1: Set curr = root, sum = 0.
  2. Step 2: If curr.right == null: sum += curr.val; curr.val = sum; curr = curr.left.
  3. Step 3: Else find leftmost node in curr.right (succ).
  4. Step 4: If succ.left == null: succ.left = curr, curr = curr.right.
  5. Step 5: Else: succ.left = null, sum += curr.val; curr.val = sum; curr = curr.left.
  6. Step 6: Return root.

Convert BST to Greater Tree Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Descending visit node 6: sum = 6 -> val becomes 6
Visual state
Values and pointers at this exact step
tree
This tree trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Decision / next transition
Step 1
Why this step matters

Descending visit node 6: sum = 6 -> val becomes 6.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode *left, *right;
7 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11public:
12 TreeNode* convertBST(TreeNode* root) {
13 int sum = 0;
14 TreeNode* curr = root;
15 while (curr) {
16 if (!curr->right) {
17 sum += curr->val;
18 curr->val = sum;
19 curr = curr->left;
20 } else {
21 TreeNode* succ = curr->right;
22 while (succ->left && succ->left != curr) succ = succ->left;
23 if (!succ->left) {
24 succ->left = curr;
25 curr = curr->right;
26 } else {
27 succ->left = nullptr;
28 sum += curr->val;
29 curr->val = sum;
30 curr = curr->left;
31 }
32 }
33 }
34 return root;
35 }
36};
37
38int main() {
39 TreeNode* root = new TreeNode(4);
40 root->left = new TreeNode(1);
41 root->right = new TreeNode(6);
42 Solution sol;
43 sol.convertBST(root);
44 cout << "Morris Root: " << root->val << ", Left: " << root->left->val << ", Right: " << root->right->val << endl;
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(1) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Two-Pass Suffix ArrayO(N)O(N)Collect nodes, compute suffix sum, overwrite.Memory allocation.
2.Reverse Inorder DFSO(N)O(H)Right -> Root -> Left with running sum.Call stack depth.
3.Reverse Morris Traversal (Optimal)OptimalO(N)O(1)Threaded binary tree traversal in reverse.None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Standard inorder traversal instead of reverse inorder

Traversing Left -> Root -> Right computes prefix sums (smaller elements) instead of greater elements.

Forgetting to reset running sum

If sum is a class variable, failing to reset sum = 0 produces wrong answers across multiple test cases.

Modifying tree structure permanently in Morris

Failing to restore succ.left = null corrupts the tree topology.

Crucial Edge Cases to Validate:

  • Empty tree (root == null) — Returns null.
  • Single node tree — Value remains unchanged (sum = val).
  • Tree with negative values — Addition works consistently in two's complement.
  • Skewed tree — Handled in O(N) time without stack overflow.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the key symmetry immediately: 'Standard inorder gives ascending order; reverse inorder (Right -> Root -> Left) gives descending order.'
  2. Write the concise 5-line recursive DFS solution.
  3. Mention Reverse Morris Traversal as an O(1) auxiliary space optimization to stand out.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does reversing the inorder traversal order (Right -> Node -> Left) work for this problem?

2.What is the time complexity of the Reverse Inorder DFS approach?

3.In Reverse Morris Traversal, which child pointer of the successor is temporarily linked back to curr?

Back to DSA Sheet