Convert BST to Greater Tree

Medium
1923.

Convert BST to Greater Tree

Convert BST to Greater Tree is a medium coding problem on depth-first search, binary search and trees, asked in Amazon and Meta interviews.

You are given the root of a binary search tree whose values are all distinct. Turn it into a greater tree: replace every node's value with the sum of its original value and all values in the tree that are greater than it. Keep the tree's shape and return its root.

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]
Explanation
The largest value, 8, stays 8; 7 becomes 7 + 8 = 15; 6 becomes 6 + 7 + 8 = 21; and so on down to 0, which becomes the sum of every value, 36.

Example 2

Input
root = [0,null,1]
Output
[1,null,1]
Explanation
1 has nothing greater and stays 1; 0 becomes 0 + 1 = 1.

Example 3

Input
root = []
Output
[]
Explanation
An empty tree stays empty.

Constraints

  • The number of nodes in the tree is in the range [0, 10^4]
  • -10^4 <= Node.val <= 10^4
  • All the values in the tree are unique
  • root is guaranteed to be a valid binary search tree
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var convertBST = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Convert BST to Greater Tree — Solution in Python, Java & C++

Convert BST to Greater Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Convert BST to Greater Tree is a medium coding problem on depth-first search, binary search and trees, asked in Amazon and Meta interviews.

Problem statement

You are given the root of a binary search tree whose values are all distinct. Turn it into a greater tree: replace every node's value with the sum of its original value and all values in the tree that are greater than it. Keep the tree's shape and return its root.

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]
Explanation: The largest value, 8, stays 8; 7 becomes 7 + 8 = 15; 6 becomes 6 + 7 + 8 = 21; and so on down to 0, which becomes the sum of every value, 36.

Example 2

Input: root = [0,null,1]
Output: [1,null,1]
Explanation: 1 has nothing greater and stays 1; 0 becomes 0 + 1 = 1.

Example 3

Input: root = []
Output: []
Explanation: An empty tree stays empty.

Constraints

  • The number of nodes in the tree is in the range [0, 10^4]
  • -10^4 <= Node.val <= 10^4
  • All the values in the tree are unique
  • root is guaranteed to be a valid binary search tree

Hints for Convert BST to Greater Tree

  1. Hint 1

    Which nodes are greater than a given node? In a search tree, they are exactly the ones an in-order walk visits after it.

  2. Hint 2

    Walk the tree in reverse in-order — right subtree, node, left subtree — so the nodes come largest first.

  3. Hint 3

    Keep one running total across the whole walk: add each node's value to it, then write the total back into the node.

How to solve Convert BST to Greater Tree

An in-order walk of a BST lists values in increasing order, so the reverse walk (right, node, left) lists them in decreasing order. A running sum along that walk is, at each node, the sum of that node and everything greater.

Approach

  1. Keep an accumulator acc = 0 shared by the whole walk.
  2. Visit a node: first recurse into its right subtree.
  3. Then add the node's value to acc and set the node's value to acc.
  4. Then recurse into its left subtree. Return the root when the walk ends.

Why it works

When a node is reached in reverse in-order, every node with a greater value has already been visited and added to acc, and no smaller one has. So acc + node.val is exactly the required sum.

Complexity

  • Time — O(n)
  • Space — O(h) for the recursion, h being the tree's height

Pitfalls

  • The accumulator must persist across recursive calls — pass it by reference or keep it outside the recursion.
  • Add the node's original value before overwriting it; the overwritten value is the new total.
  • Going left first produces sums of smaller values instead.

Reference solution

Python

from typing import Optional

def convertBST(root: Optional[TreeNode]) -> Optional[TreeNode]:
    acc = 0
    stack = []
    node = root
    while node is not None or stack:
        while node is not None:
            stack.append(node)
            node = node.right
        node = stack.pop()
        acc += node.val
        node.val = acc
        node = node.left
    return root

Java

public static TreeNode convertBST(TreeNode root) {
    int acc = 0;
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode node = root;
    while (node != null || !stack.isEmpty()) {
        while (node != null) {
            stack.push(node);
            node = node.right;
        }
        node = stack.pop();
        acc += node.val;
        node.val = acc;
        node = node.left;
    }
    return root;
}

C++

void greaterWalk(TreeNode* node, int& acc);

TreeNode* convertBST(TreeNode* root) {
    int acc = 0;
    greaterWalk(root, acc);
    return root;
}

void greaterWalk(TreeNode* node, int& acc) {
    if (!node) return;
    greaterWalk(node->right, acc);
    acc += node->val;
    node->val = acc;
    greaterWalk(node->left, acc);
}

JavaScript

var convertBST = function(root) {
    var acc = 0, stack = [], node = root;
    while (node !== null || stack.length > 0) {
        while (node !== null) {
            stack.push(node);
            node = node.right;
        }
        node = stack.pop();
        acc += node.val;
        node.val = acc;
        node = node.left;
    }
    return root;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Search