Convert BST to Greater Tree solution and explanation
Google
9 more videos on this problem
Convert BST to Greater Tree - Leetcode 538 - PythonNeetCode · 9:33 · 28K views
Convert BST to Greater Tree | Live Coding with Explanation | Leetcode #538Algorithms Made Easy · 5:48 · 5K views
[Reverse Morris InOrder] Convert BST to Greater Tree | Live Coding with Explanation | Leetcode #538Algorithms Made Easy · 9:01 · 1K views
Convert BST to Greater Tree | Leetcode 538 | Leetcode 1038Coding Decoded · 9:10 · 1K views
Convert BST to Greater Tree | Leetcode 538 | Binary Search Tree 🔥🔥 | Live coding sessionCoding Decoded · 2:13 · 558 views
Baozi Training Leetcode 538 solution: Convert BST to Greater TreeBaozi Training · 5:13 · 555 views
GOOGLE Coding Interview Question • Convert BST To Greater Tree • Leetcode 538Abhyuday Dixit · 16:46 · 353 views
Daily Leetcode #315: Feb 09, 2021 - 538. Convert BST to Greater TreeProgramming Live with Larry · 14:36 · 218 views
Daily Leetcode #746: Apr 16, 2022 - 538. Convert BST to Greater TreeProgramming Live with Larry · 16:19 · 191 views
Guide for converting BST to Greater Tree | Smart Sessions - Smart InterviewsSmart Interviews · 8:51 · 763 views
The problem
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.
As a reminder, a binary search tree is a tree that satisfies these constraints:
- 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.
Example 1:
Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
Example 2:
Input: root = [0,null,1] Output: [1,null,1]
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.
rootis guaranteed to be a valid binary search tree.
Note: This question is the same as 1038: https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/
Approach overview
Problem Overview: You are given a Binary Search Tree where each node must be updated to contain its original value plus the sum of all keys greater than it. The BST ordering property (left < root < right) is the key observation that makes the problem solvable efficiently.
Approach 1: Reverse Inorder Traversal (O(n) time, O(h) space)
A Binary Search Tree visited in normal inorder produces values in ascending order. Reversing the order (right → root → left) processes nodes from largest to smallest. Maintain a running sum of visited node values. When visiting a node, add the running sum to its value, then update the sum. This works because every node encountered earlier in reverse inorder is guaranteed to have a greater value. The traversal can be implemented using recursion or an explicit stack via depth-first search. Time complexity is O(n) since every node is visited once, and auxiliary space is O(h) where h is the tree height due to the recursion stack.
Approach 2: Morris Traversal (O(n) time, O(1) space)
Morris traversal eliminates the recursion stack by temporarily modifying tree pointers during traversal. For this problem, perform a reverse Morris traversal (right → root → left). For each node, locate its inorder successor and create a temporary threaded link back to the current node. This allows returning after exploring the right subtree without a stack. Maintain the same running sum logic used in the DFS solution. After processing, restore all modified pointers so the tree structure remains intact. The traversal still visits each node a constant number of times, giving O(n) time and O(1) extra space. This approach is useful when strict memory constraints exist or when recursion depth might become large.
Recommended for interviews: Reverse inorder traversal is the solution most interviewers expect. It directly leverages the tree ordering property and is easy to reason about. Mentioning Morris traversal shows deeper knowledge of traversal optimization and space reduction, but the recursive DFS approach usually communicates the core insight more clearly during interviews.
Approach 1: Reverse Inorder Traversal Approach
This approach leverages the property of Binary Search Trees where the nodes in the right subtree are greater than those in the left subtree. By performing a reverse inorder traversal (right -> root -> left), we can accumulate the sum of all nodes greater than the current node and update each node with this accumulated sum. The traversal ensures that we always process the greater nodes first.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def __init__(self):
self.sum = 0
def convertBST(self, root: TreeNode) -> TreeNode:
if root:
self.convertBST(root.right)
self.sum += root.val
root.val = self.sum
self.convertBST(root.left)
return rootclass TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
private int sum = 0;
public TreeNode convertBST(TreeNode root) {
if (root != null) {
convertBST(root.right);
sum += root.val;
root.val = sum;
convertBST(root.left);
}
return root;
}
}#include <iostream>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
int sum = 0;
public:
TreeNode* convertBST(TreeNode* root) {
if (root != NULL) {
convertBST(root->right);
sum += root->val;
root->val = sum;
convertBST(root->left);
}
return root;
}
};function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
var convertBST = function(root) {
let sum = 0;
const traverse = node => {
if (node === null) return;
traverse(node.right);
sum += node.val;
node.val = sum;
traverse(node.left);
};
traverse(root);
return root;
};#include <stdio.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
void traverse(struct TreeNode* node, int* sum) {
if (node == NULL) return;
traverse(node->right, sum);
*sum += node->val;
node->val = *sum;
traverse(node->left, sum);
}
struct TreeNode* convertBST(struct TreeNode* root) {
int sum = 0;
traverse(root, &sum);
return root;
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
private int sum = 0;
public TreeNode ConvertBST(TreeNode root) {
if (root != null) {
ConvertBST(root.right);
sum += root.val;
root.val = sum;
ConvertBST(root.left);
}
return root;
}
}The Python solution uses a Solution class to encapsulate a sum attribute that keeps track of the accumulated value during traversal. The method convertBST updates the tree by performing a reverse inorder traversal.
Time Complexity: O(n), where n is the number of nodes, as each node is visited exactly once.
Space Complexity: O(h), where h is the height of the binary search tree, due to recursion depth.
Approach 2: Morris Traversal Approach
The Morris Traversal technique allows in-order traversal of a binary tree without using extra space for recursion or a stack. It modifies the tree structure during the traversal, and at the end of the traversal, the original tree structure is restored.
For this problem, we adapt the Morris Traversal to traverse the tree in reverse inorder fashion and keep track of the sum of nodes greater than the current node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def convertBST(self, root: TreeNode) -> TreeNode:
sum = 0
node = root
while node is not None:
if node.right is None:
sum += node.val
node.val = sum
node = node.left
else:
succ = node.right
while succ.left is not None and succ.left != node:
succ = succ.left
if succ.left is None:
succ.left = node
node = node.right
else:
succ.left = None
sum += node.val
node.val = sum
node = node.left
return rootThis Python solution uses the Morris Traversal technique, which allows modifying the tree without using stack or recursion explicitly. The key idea is to establish a temporary link between each node and its inorder predecessor, traverse in reverse inorder, update the nodes, and then restore the tree structure by removing the temporary links.
Time Complexity: O(n), where n is the number of nodes. Although every edge is visited at most twice, the overall complexity remains linear.
Space Complexity: O(1) since no extra space is used apart from variables.
Approach 3: Default Approach
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func convertBST(root *TreeNode) *TreeNode {
s := 0
var dfs func(*TreeNode)
dfs = func(root *TreeNode) {
if root == nil {
return
}
dfs(root.Right)
s += root.Val
root.Val = s
dfs(root.Left)
}
dfs(root)
return root
}Complexity comparison
| Approach | Complexity |
|---|---|
| Reverse Inorder Traversal Approach | Time Complexity: O(n), where n is the number of nodes, as each node is visited exactly once. |
| Morris Traversal Approach | Time Complexity: O(n), where n is the number of nodes. Although every edge is visited at most twice, the overall complexity remains linear. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Reverse Inorder Traversal (DFS) | O(n) | O(h) | Standard interview solution. Simple recursion leveraging BST ordering. |
| Morris Reverse Traversal | O(n) | O(1) | Useful when minimizing auxiliary memory or avoiding recursion stack. |
Frequently asked questions
Is Convert BST to Greater Tree easy or hard?
Convert BST to Greater Tree is classified as a Medium problem. The main challenge is recognizing that reverse inorder traversal naturally processes nodes from largest to smallest, which enables maintaining a running sum efficiently.
Convert BST to Greater Tree Python/Java solution
Both Python and Java implementations typically use recursive reverse inorder traversal. A global or class-level running sum variable tracks the accumulated value, and each visited node updates its value with that sum. The algorithm runs in O(n) time and O(h) stack space.
How to solve Convert BST to Greater Tree in O(n)?
Traverse the BST in reverse inorder (right → root → left). Maintain a running variable storing the sum of all previously visited nodes. Update each node by adding this running sum, then update the sum with the node's new value. Since each node is processed once, the total runtime is O(n).
What is the best approach for Convert BST to Greater Tree?
Reverse inorder traversal is the most common solution. By visiting nodes in the order right → root → left, you process values from largest to smallest and maintain a running sum of previously visited nodes. Each node adds this sum to its value, producing the correct greater tree in O(n) time.
Is Convert BST to Greater Tree asked at Google/Amazon/Meta?
BST transformation problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variations of this problem test understanding of BST properties, depth-first traversal, and tree manipulation during recursion.
What data structure is used in Convert BST to Greater Tree?
The primary data structure is a Binary Search Tree. The algorithm relies on the BST ordering property and uses depth-first search traversal, either through recursion, an explicit stack, or Morris traversal for constant extra space.
What is the time complexity of Convert BST to Greater Tree?
The optimal time complexity is O(n) because every node in the tree must be visited exactly once. Space complexity is O(h) with recursive DFS where h is the height of the tree, or O(1) when using Morris traversal.