Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Binary Search Tree to Greater Sum Tree solution and explanation

MediumBinary Search TreeBinary TreeDepth-First SearchTree7 min read88.3% acceptanceUpdated 9 Apr 2026
Asked atSAPAmazonGoogle
Practise Binary Search Tree to Greater Sum Tree
27:38
Binary Search Tree to Greater Sum Tree | Brute | Better | Optimal | Leetcode 1038 | codestorywithMIKcodestorywithMIK · 27:38 · 9K viewsWatch on YouTube
9 more videos on this problem
  1. Binary Search Tree to Greater Sum Tree | Brute | Better | Optimal | Leetcode 1038 | codestorywithMIKcodestorywithMIK · 27:38 · 9K views
  2. 1038. Binary Search Tree to Greater Sum Tree | Recursive | Iterative | Morris TraversalAryan Mittal · 34:27 · 3K views
  3. LeetCode #1038 - Binary Search Tree to Greater Sum TreeEugene Suleimanov · 7:03 · 2K views
  4. Binary Search Tree to Greater Sum Tree | Leetcode 1038Ayushi Sharma · 11:51 · 1K views
  5. 1038. Binary Search Tree to Greater Sum Tree - English VersionSimple Code - 단순코드 · 5:48 · 1K views
  6. Convert BST to Greater Tree | Leetcode 538 | Leetcode 1038Coding Decoded · 9:10 · 1K views
  7. ✅ Binary Search Tree to Greater Sum Tree - LeetCode 1038 - Reverse Inorder Traversal - ExplainedLeet Logics · 8:09 · 1K views
  8. 1038. Binary Search Tree to Greater Sum Tree (Leetcode Medium)Programming Live with Larry · 11:09 · 471 views
  9. leetCode 1038 - Binary Search Tree to Greater Sum Tree | JSer - algorithm & JavaScriptJSer · 16:10 · 406 views
  10. LeetCode 1038 Binary Search Tree to Greater Sum TreeAlgorithmicIQ · 5:31 · 333 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 [1, 100].
  • 0 <= Node.val <= 100
  • All the values in the tree are unique.

Note: This question is the same as 538: https://leetcode.com/problems/convert-bst-to-greater-tree/

Approach overview

Problem Overview: You are given a binary search tree where each node must be updated so its new value equals the original value plus the sum of all keys greater than it. The structure of the tree stays the same; only node values change.

Approach 1: Reverse In-Order Traversal (DFS) (Time: O(n), Space: O(h))

A BST visited in reverse in-order order (right → node → left) processes nodes from largest to smallest. Maintain a running variable sum that stores the cumulative total of nodes already visited. When you reach a node, add its value to sum and update the node with this new total. Because nodes are visited in descending order, sum always represents the sum of all greater values. This approach relies on depth-first search and the ordering property of a BST. The recursion depth equals the tree height h, giving O(h) auxiliary space. For balanced trees this is O(log n), while a skewed tree degrades to O(n).

The key insight is exploiting the BST ordering. Instead of computing greater sums by scanning other nodes, you accumulate them naturally while traversing from the largest value downward. This produces an optimal linear-time solution and minimal extra state.

Approach 2: Iterative Traversal Using a Stack (Time: O(n), Space: O(h))

The same reverse in-order logic can be implemented iteratively with an explicit stack. Start from the root and push nodes while moving right to reach the maximum element. Pop a node, update the running sum, modify the node value, then move to its left subtree. Repeat the process until the stack becomes empty. Each node is pushed and popped once, keeping the time complexity O(n).

This approach avoids recursion and is useful in environments where stack depth is a concern. The stack stores at most the height of the tree, so space complexity remains O(h). The algorithm still leverages the sorted property of a binary tree structured as a BST, ensuring nodes are processed in descending order.

Recommended for interviews: Reverse in-order traversal is the expected solution. It demonstrates understanding of BST ordering and how DFS traversal patterns can transform data efficiently. Mentioning the iterative stack variant shows awareness of recursion limits and gives a practical alternative while keeping the same O(n) performance.

Approach 1: Reverse In-Order Traversal

A reverse in-order traversal (right-root-left) allows us to visit nodes in decreasing order of their values in a BST. By maintaining a cumulative sum during this traversal, we can update each node with the sum of all nodes that have been visited so far, effectively converting it into a Greater Sum Tree.

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 bstToGst(self, root: TreeNode) -> TreeNode:
        if root is not None:
            self.bstToGst(root.right)
            self.sum += root.val
            root.val = self.sum
            self.bstToGst(root.left)
        return root
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    private void transform(TreeNode node, int[] sum) {
        if (node == null) return;
        transform(node.right, sum);
        sum[0] += node.val;
        node.val = sum[0];
        transform(node.left, sum);
    }

    public TreeNode bstToGst(TreeNode root) {
        int[] sum = new int[1];
        transform(root, sum);
        return root;
    }
}
#include<iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    void transform(TreeNode* node, int& sum) {
        if (!node) return;
        transform(node->right, sum);
        sum += node->val;
        node->val = sum;
        transform(node->left, sum);
    }

    TreeNode* bstToGst(TreeNode* root) {
        int sum = 0;
        transform(root, sum);
        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 bstToGst = function(root) {
    let sum = 0;
    const transform = (node) => {
        if (node === null) return;
        transform(node.right);
        sum += node.val;
        node.val = sum;
        transform(node.left);
    };
    transform(root);
    return root;
};
#include<stdio.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void transform(struct TreeNode* node, int* sum) {
    if (node == NULL) return;
    transform(node->right, sum);
    *sum += node->val;
    node->val = *sum;
    transform(node->left, sum);
}

struct TreeNode* bstToGst(struct TreeNode* root) {
    int sum = 0;
    transform(root, &sum);
    return root;
}
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    private int sum = 0;

    public TreeNode BstToGst(TreeNode root) {
        if (root != null) {
            BstToGst(root.right);
            sum += root.val;
            root.val = sum;
            BstToGst(root.left);
        }
        return root;
    }
}

This Python solution uses a class variable to store the cumulative sum during the reverse in-order traversal. The solution reflects a direct transformation of the BST to a Greater Sum Tree.

Complexity

The time complexity is O(n) because each node is visited once, where n is the number of nodes. Space complexity is O(h), with h being the tree's height, representing the recursion stack.

Try this approach in the editor

Approach 2: Iterable Approach Using a Stack

We can emulate the recursive reverse in-order traversal with an iterative approach using a stack. By processing the nodes in decreasing order of their values, we maintain a sum of all visited nodes and update each node accordingly.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def bstToGst(self, root: TreeNode) -> TreeNode:
        stack, node, sum = [], root, 0
        while stack or node is not None:
            while node is not None:
                stack.append(node)
                node = node.right
            node = stack.pop()
            sum += node.val
            node.val = sum
            node = node.left
        return root
import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public TreeNode bstToGst(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        int sum = 0;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.right;
            }
            node = stack.pop();
            sum += node.val;
            node.val = sum;
            node = node.left;
        }
        return root;
    }
}
#include<iostream>
#include<stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* bstToGst(TreeNode* root) {
        stack<TreeNode*> s;
        TreeNode* node = root;
        int sum = 0;
        while (!s.empty() || node != NULL) {
            while (node != NULL) {
                s.push(node);
                node = node->right;
            }
            node = s.top(); s.pop();
            sum += node->val;
            node->val = sum;
            node = node->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 bstToGst = function(root) {
    let stack = [];
    let node = root;
    let sum = 0;
    while (stack.length > 0 || node !== null) {
        while (node !== null) {
            stack.push(node);
            node = node.right;
        }
        node = stack.pop();
        sum += node.val;
        node.val = sum;
        node = node.left;
    }
    return root;
};
#include<stdio.h>
#include<stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode* bstToGst(struct TreeNode* root) {
    struct TreeNode* stack[100];
    int top = -1;
    struct TreeNode* node = root;
    int sum = 0;
    while (top >= 0 || node != NULL) {
        while (node != NULL) {
            stack[++top] = node;
            node = node->right;
        }
        node = stack[top--];
        sum += node->val;
        node->val = sum;
        node = node->left;
    }
    return root;
}
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public TreeNode BstToGst(TreeNode root) {
        var stack = new Stack<TreeNode>();
        var node = root;
        int sum = 0;
        while (stack.Count > 0 || node != null) {
            while (node != null) {
                stack.Push(node);
                node = node.right;
            }
            node = stack.Pop();
            sum += node.val;
            node.val = sum;
            node = node.left;
        }
        return root;
    }
}

This Python version maintains a stack for iterating nodes in the sequence and calculating updated values on the go, without deep recursion reliance.

Complexity

The solution's time complexity is O(n), iterating all n nodes. Space use is O(h) regarding the stack storage requirement in correlation with tree depth.

Try this approach in the editor

Approach 3: Recursion

Traverse the binary search tree in the order of "right-root-left". Accumulate all the node values encountered into s, and assign the accumulated value to the corresponding node.

Time complexity is O(n), and space complexity is O(n), where n is the number of nodes in the binary search tree.

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function bstToGst(root: TreeNode | null): TreeNode | null {
    let s = 0;
    const dfs = (root: TreeNode | null) => {
        if (!root) {
            return;
        }
        dfs(root.right);
        s += root.val;
        root.val = s;
        dfs(root.left);
    };
    dfs(root);
    return root;
}
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func bstToGst(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
}
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    pub fn bst_to_gst(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        let mut s = 0;
        Self::dfs(&root, &mut s);
        root
    }

    fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, s: &mut i32) {
        if let Some(node) = root {
            let mut node = node.borrow_mut();
            Self::dfs(&node.right, s);
            *s += node.val;
            node.val = *s;
            Self::dfs(&node.left, s);
        }
    }
}
Try this approach in the editor

Approach 4: Morris Traversal

Morris traversal does not require a stack, with a time complexity of O(n) and a space complexity of O(1). The core idea is as follows:

Define s as the cumulative sum of the node values in the binary search tree. Traverse the binary tree nodes:

  1. If the right subtree of the current node root is null, add the current node value to s, update the current node value to s, and move the current node to root.left.
  2. If the right subtree of the current node root is not null, find the leftmost node next in the right subtree (i.e., the successor node of root in an in-order traversal):
    • If the left subtree of the successor node next is null, set the left subtree of next to point to the current node root, and move the current node to root.right.
    • If the left subtree of the successor node next is not null, add the current node value to s, update the current node value to s, then set the left subtree of next to null (i.e., remove the link between next and root), and move the current node to root.left.
  3. Repeat the above steps until the binary tree nodes are null, at which point the traversal is complete.
  4. Finally, return the root node of the binary search tree.

Morris reverse in-order traversal follows the same idea as Morris in-order traversal, except that the traversal order changes from "left-root-right" to "right-root-left".

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function bstToGst(root: TreeNode | null): TreeNode | null {
    let cur = root;
    let sum = 0;
    while (cur != null) {
        const { val, left, right } = cur;
        if (right == null) {
            sum += val;
            cur.val = sum;
            cur = left;
        } else {
            let next = right;
            while (next.left != null && next.left != cur) {
                next = next.left;
            }
            if (next.left == null) {
                next.left = cur;
                cur = right;
            } else {
                next.left = null;
                sum += val;
                cur.val = sum;
                cur = left;
            }
        }
    }
    return root;
}
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func bstToGst(root *TreeNode) *TreeNode {
	s := 0
	node := root
	for root != nil {
		if root.Right == nil {
			s += root.Val
			root.Val = s
			root = root.Left
		} else {
			next := root.Right
			for next.Left != nil && next.Left != root {
				next = next.Left
			}
			if next.Left == nil {
				next.Left = root
				root = root.Right
			} else {
				s += root.Val
				root.Val = s
				next.Left = nil
				root = root.Left
			}
		}
	}
	return node
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Reverse In-Order Traversal

The time complexity is O(n) because each node is visited once, where n is the number of nodes. Space complexity is O(h), with h being the tree's height, representing the recursion stack.

Iterable Approach Using a Stack

The solution's time complexity is O(n), iterating all n nodes. Space use is O(h) regarding the stack storage requirement in correlation with tree depth.

Recursion–
Morris Traversal–

Complexity analysis

ApproachTimeSpaceWhen to Use
Reverse In-Order Traversal (DFS)O(n)O(h)Preferred solution for BST problems; simple and optimal when recursion depth is manageable.
Iterative Traversal Using StackO(n)O(h)Useful when avoiding recursion or when stack overflow risk exists for deep trees.

Frequently asked questions

Is Binary Search Tree to Greater Sum Tree easy or hard?

The problem is rated Medium on LeetCode. The implementation is short, but recognizing that reverse in-order traversal processes nodes in descending order is the key insight that makes the solution straightforward.

Binary Search Tree to Greater Sum Tree Python/Java solution

In Python or Java, the typical implementation uses a recursive DFS with a global running sum variable. Traverse right, update the node with the cumulative sum, then traverse left. Both languages achieve O(n) time and O(h) space with this approach.

How to solve Binary Search Tree to Greater Sum Tree in O(n)?

Traverse the BST using reverse in-order traversal (right → node → left). Maintain a global or external variable storing the cumulative sum of previously visited nodes. Update each node by adding the running sum, then update the running sum with the node's new value. Since each node is processed once, the complexity remains O(n).

What is the best approach for Binary Search Tree to Greater Sum Tree?

Reverse in-order traversal is the best approach. Visiting nodes in the order right → node → left processes BST values from largest to smallest, allowing you to maintain a running sum of greater values. Each node is updated once, giving O(n) time and O(h) space where h is the tree height.

Is Binary Search Tree to Greater Sum Tree asked at Google/Amazon/Meta?

BST transformation and traversal problems like this appear frequently in interviews at companies such as Amazon, Google, and Meta. Interviewers often use variations that test understanding of in-order traversal, reverse traversal, and maintaining state during DFS.

What data structure is used in Binary Search Tree to Greater Sum Tree?

The main data structure is a Binary Search Tree. The algorithm also uses recursion or a stack to perform depth-first traversal while maintaining a running sum of previously processed nodes.

What is the time complexity of Binary Search Tree to Greater Sum Tree?

The optimal solution runs in O(n) time because every node in the BST is visited exactly once during traversal. The auxiliary space is O(h), where h is the height of the tree, due to recursion stack or an explicit stack in the iterative version.

Comments

Now write it yourselfClose this page and solve Binary Search Tree to Greater Sum Tree in the editor, without looking.
Practise Binary Search Tree to Greater Sum Tree