Convert BST to Greater Tree - Practice Coding Problems

Convert BST to Greater Tree - 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.

Input & Output

Example 1 — Basic BST

$ 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]

💡 Note: For each node, add sum of all greater values. Node 4 becomes 4+5+6+7+8=30, node 1 becomes 1+2+3+4+5+6+7+8=36, etc.

Example 2 — Smaller BST

$ Input: root = [0,null,1]

› Output: [1,null,1]

💡 Note: Node 0 becomes 0+1=1 (sum of greater values), node 1 stays 1 (no greater values exist)

Example 3 — Single Node

$ Input: root = [1]

› Output: [1]

💡 Note: Single node has no greater values, so it remains unchanged

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Original BST

Input BST with values [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]

Calculate Sums

For each node, find sum of all nodes with greater values

Updated BST

Each node = original value + sum of greater values

Key Takeaway

🎯 Key Insight: Use reverse in-order traversal to process nodes from largest to smallest, maintaining a running sum for optimal O(n) performance

Asked in

a Amazon 15 f Facebook 12 G Google 8 m Microsoft 6

The key insight is to use reverse in-order traversal (right-root-left) which naturally processes BST nodes from largest to smallest. This allows us to maintain a running sum of all previously visited (larger) nodes and update each current node efficiently. Best approach is Reverse In-Order DFS with Time: O(n), Space: O(h).

Common Approaches

Approach	Time	Space	Notes
✓ Reverse In-Order DFS	O(n)	O(h)	Use reverse in-order traversal (right-root-left) to process nodes from largest to smallest
Brute Force - For Each Node Calculate Sum	O(n²)	O(h)	For each node, traverse the entire tree to find sum of larger values

Reverse In-Order DFS — Algorithm Steps

Step 1: Traverse right subtree first (larger values)
Step 2: Update current node with running sum
Step 3: Add current node to running sum
Step 4: Traverse left subtree (smaller values)

Visualization

Tap to expand

Step-by-Step Walkthrough

Visit Right First

Process 8→7→6→5→4→3→2→1→0 (largest to smallest)

Running Sum

8: +0=8, 7: +8=15, 6: +15=21, 5: +21=26, 4: +26=30

Final Tree

All nodes updated with sum of greater values

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

int runningSum = 0;

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void reverseInorder(struct TreeNode* node) {
    if (!node) return;
    
    // Traverse right subtree first (larger values)
    reverseInorder(node->right);
    
    // Update current node with sum of all larger values
    node->val += runningSum;
    runningSum = node->val;
    
    // Traverse left subtree (smaller values)
    reverseInorder(node->left);
}

struct TreeNode* solution(struct TreeNode* root) {
    runningSum = 0;
    reverseInorder(root);
    return root;
}

void printInorder(struct TreeNode* root) {
    if (!root) {
        printf("null,");
        return;
    }
    printf("%d,", root->val);
    printInorder(root->left);
    printInorder(root->right);
}

int main() {
    struct TreeNode* root = createNode(4);
    root->left = createNode(1);
    root->right = createNode(6);
    root->left->left = createNode(0);
    root->left->right = createNode(2);
    root->right->left = createNode(5);
    root->right->right = createNode(7);
    root->left->right->right = createNode(3);
    root->right->right->right = createNode(8);
    
    struct TreeNode* result = solution(root);
    printf("[");
    printInorder(result);
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once in reverse in-order traversal

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h (O(log n) balanced, O(n) worst case)

✓ Linear Space

125.0K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Reverse In-Order DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler