Convert BST to Greater Tree

🎯

Convert BST to Greater Tree

mediumTREEAmazonGoogleFacebook

Imagine you have a database of user scores stored in a BST, and you want to update each score to reflect the sum of all scores greater than or equal to it, to quickly answer ranking queries.

💡 This problem involves transforming a BST by accumulating values from nodes with greater keys. Beginners often struggle because it requires understanding BST properties and a traversal order that is not the usual inorder.

📋

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 the BST. Return the root of the modified tree.

The number of nodes in the tree is in the range [1, 10^5].0 <= Node.val <= 10^4The given tree is a valid binary search tree.

💡

Example

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]

Traverse the BST in reverse inorder (right-root-left), accumulate the sum of visited nodes, and update each node's value to this sum.

• Single node tree → node value remains the same
• All nodes have the same value → each node updated to value * number of nodes
• Right skewed tree → values accumulate from bottom to top
• Left skewed tree → values accumulate from rightmost leaf to root

⚠️

Common Mistakes

Using inorder traversal instead of reverse inorder

Nodes get updated incorrectly because smaller nodes are processed before larger ones

✅ Use reverse inorder traversal (right-root-left) to process nodes from largest to smallest

Resetting accumulated sum inside recursive calls

Sum does not accumulate across nodes, resulting in incorrect values

✅ Keep accumulated sum as a class variable or external variable that persists across calls

Not handling null nodes before recursion

Null pointer exceptions or runtime errors occur

✅ Check if node is null before recursive calls

Modifying node values before traversing right subtree

Sum is incorrect because right subtree nodes are not yet included

✅ Traverse right subtree first, then update current node

Using global variables without resetting between test cases

Incorrect results when running multiple test cases in same session

✅ Reset global or class variables before each test case

🧠

Brute Force (Inorder Traversal + For Each Node Sum)

💡 This approach exists to build intuition by directly applying the problem definition: for each node, sum all nodes with greater values. It is simple but inefficient, highlighting the need for better methods.

Intuition

For each node, traverse the entire tree to find and sum all nodes with values greater than the current node's value, then update the node's value.

Algorithm

1. Traverse the BST in any order to visit each node.
2. For each node, traverse the entire tree again to sum values greater than the current node's value (excluding the node itself).
3. Update the current node's value with this sum plus its original value.
4. Return the root of the updated tree.

💡 This algorithm is straightforward but involves nested traversals, making it inefficient and hard to scale.

</>

Code

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

def sum_greater(root, val, exclude_node):
    if not root:
        return 0
    total = 0
    if root != exclude_node and root.val > val:
        total += root.val
    total += sum_greater(root.left, val, exclude_node)
    total += sum_greater(root.right, val, exclude_node)
    return total

def convertBST(root):
    if not root:
        return None
    root.val += sum_greater(root, root.val, root)
    convertBST(root.left)
    convertBST(root.right)
    return root

# Driver code to test
if __name__ == '__main__':
    # Construct example tree
    root = TreeNode(4,
                    TreeNode(1,
                             TreeNode(0),
                             TreeNode(2, None, TreeNode(3))),
                    TreeNode(6,
                             TreeNode(5),
                             TreeNode(7, None, TreeNode(8))))
    new_root = convertBST(root)
    # Simple inorder print to verify
    def inorder(node):
        return inorder(node.left) + [node.val] + inorder(node.right) if node else []
    print(inorder(new_root))

Line Notes

class TreeNode:Defines the tree node structure with value and left/right children

def sum_greater(root, val, exclude_node):Helper function to sum nodes with values greater than val excluding the current node

if root != exclude_node and root.val > val:Add node's value only if it is strictly greater than current node's value and not the node itself

root.val += sum_greater(root, root.val, root)Update current node's value by adding sum of greater values excluding itself

convertBST(root.left)Recursively update left subtree nodes

convertBST(root.right)Recursively update right subtree nodes

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

public class Solution {
    public int sumGreater(TreeNode root, int val, TreeNode excludeNode) {
        if (root == null) return 0;
        int total = 0;
        if (root != excludeNode && root.val > val) total += root.val;
        total += sumGreater(root.left, val, excludeNode);
        total += sumGreater(root.right, val, excludeNode);
        return total;
    }

    public TreeNode convertBST(TreeNode root) {
        if (root == null) return null;
        root.val += sumGreater(root, root.val, root);
        convertBST(root.left);
        convertBST(root.right);
        return root;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(1);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(2);
        root.left.right.right = new TreeNode(3);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(7);
        root.right.right.right = new TreeNode(8);

        Solution sol = new Solution();
        TreeNode newRoot = sol.convertBST(root);

        // Inorder print
        inorderPrint(newRoot);
    }

    static void inorderPrint(TreeNode node) {
        if (node == null) return;
        inorderPrint(node.left);
        System.out.print(node.val + " ");
        inorderPrint(node.right);
    }
}

Line Notes

class TreeNode {Defines the tree node structure with value and left/right children

public int sumGreater(TreeNode root, int val, TreeNode excludeNode)Helper method to sum nodes with values greater than val excluding the current node

if (root != excludeNode && root.val > val) total += root.val;Add node's value only if greater than current node's value and not the node itself

root.val += sumGreater(root, root.val, root);Update current node's value by adding sum of greater values excluding itself

convertBST(root.left);Recursively update left subtree

convertBST(root.right);Recursively update right subtree

#include <iostream>
using namespace std;

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

int sumGreater(TreeNode* root, int val, TreeNode* excludeNode) {
    if (!root) return 0;
    int total = 0;
    if (root != excludeNode && root->val > val) total += root->val;
    total += sumGreater(root->left, val, excludeNode);
    total += sumGreater(root->right, val, excludeNode);
    return total;
}

TreeNode* convertBST(TreeNode* root) {
    if (!root) return NULL;
    root->val += sumGreater(root, root->val, root);
    convertBST(root->left);
    convertBST(root->right);
    return root;
}

void inorderPrint(TreeNode* root) {
    if (!root) return;
    inorderPrint(root->left);
    cout << root->val << " ";
    inorderPrint(root->right);
}

int main() {
    TreeNode* root = new TreeNode(4);
    root->left = new TreeNode(1);
    root->right = new TreeNode(6);
    root->left->left = new TreeNode(0);
    root->left->right = new TreeNode(2);
    root->left->right->right = new TreeNode(3);
    root->right->left = new TreeNode(5);
    root->right->right = new TreeNode(7);
    root->right->right->right = new TreeNode(8);

    TreeNode* newRoot = convertBST(root);
    inorderPrint(newRoot);
    cout << endl;
    return 0;
}

Line Notes

struct TreeNode {Defines the tree node structure with value and left/right children

int sumGreater(TreeNode* root, int val, TreeNode* excludeNode)Helper function to sum nodes with values greater than val excluding the current node

if (root != excludeNode && root->val > val) total += root->val;Add node's value only if greater than current node's value and not the node itself

root->val += sumGreater(root, root->val, root);Update current node's value by adding sum of greater values excluding itself

convertBST(root->left);Recursively update left subtree

convertBST(root->right);Recursively update right subtree

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

function sumGreater(root, val, excludeNode) {
    if (!root) return 0;
    let total = 0;
    if (root !== excludeNode && root.val > val) total += root.val;
    total += sumGreater(root.left, val, excludeNode);
    total += sumGreater(root.right, val, excludeNode);
    return total;
}

function convertBST(root) {
    if (!root) return null;
    root.val += sumGreater(root, root.val, root);
    convertBST(root.left);
    convertBST(root.right);
    return root;
}

// Driver code
const root = new TreeNode(4,
    new TreeNode(1,
        new TreeNode(0),
        new TreeNode(2, null, new TreeNode(3))),
    new TreeNode(6,
        new TreeNode(5),
        new TreeNode(7, null, new TreeNode(8)))
);

const newRoot = convertBST(root);

function inorder(node) {
    if (!node) return [];
    return [...inorder(node.left), node.val, ...inorder(node.right)];
}

console.log(inorder(newRoot));

Line Notes

class TreeNode {Defines the tree node structure with value and left/right children

function sumGreater(root, val, excludeNode)Helper function to sum nodes with values greater than val excluding the current node

if (root !== excludeNode && root.val > val) total += root.val;Add node's value only if greater than current node's value and not the node itself

root.val += sumGreater(root, root.val, root);Update current node's value by adding sum of greater values excluding itself

convertBST(root.left);Recursively update left subtree

convertBST(root.right);Recursively update right subtree

⏱

Complexity

TimeO(n^2)

SpaceO(n) due to recursion stack

For each of the n nodes, we traverse the entire tree (n nodes) to sum greater values, resulting in O(n^2) time. Space is O(n) due to recursion depth in worst case.

💡 For n=20, this means about 400 operations, which is inefficient for large trees.

Interview Verdict: TLE / Use only to introduce

This approach is too slow for large inputs but helps understand the problem and motivates better solutions.

🧠

Better Approach (Reverse Inorder Traversal with Accumulated Sum)

💡 This approach leverages BST properties and reverse inorder traversal to accumulate sums efficiently, avoiding repeated traversals.

Intuition

Traverse the BST in reverse inorder (right-root-left), keep a running sum of all visited nodes, and update each node's value with this sum.

Algorithm

1. Initialize a global or external variable to keep track of the accumulated sum.
2. Traverse the BST in reverse inorder: right subtree, node, left subtree.
3. At each node, add its original value to the accumulated sum.
4. Update the node's value to the accumulated sum.
5. Return the root of the updated tree.

💡 The traversal order is key and can be tricky to grasp initially, but it ensures all greater nodes are processed before the current node.

</>

Code

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.acc_sum = 0

    def convertBST(self, root):
        if root:
            self.convertBST(root.right)
            self.acc_sum += root.val
            root.val = self.acc_sum
            self.convertBST(root.left)
        return root

# Driver code
if __name__ == '__main__':
    root = TreeNode(4,
                    TreeNode(1,
                             TreeNode(0),
                             TreeNode(2, None, TreeNode(3))),
                    TreeNode(6,
                             TreeNode(5),
                             TreeNode(7, None, TreeNode(8))))
    sol = Solution()
    new_root = sol.convertBST(root)

    def inorder(node):
        return inorder(node.left) + [node.val] + inorder(node.right) if node else []
    print(inorder(new_root))

Line Notes

class Solution:Defines a class to hold the accumulated sum state across recursive calls

self.acc_sum = 0Initialize accumulated sum before traversal

self.convertBST(root.right)Traverse right subtree first to visit larger values

self.acc_sum += root.valAdd current node's value to accumulated sum

root.val = self.acc_sumUpdate node's value to accumulated sum

self.convertBST(root.left)Traverse left subtree after updating current node

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

public class Solution {
    int accSum = 0;

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

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(1);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(2);
        root.left.right.right = new TreeNode(3);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(7);
        root.right.right.right = new TreeNode(8);

        Solution sol = new Solution();
        TreeNode newRoot = sol.convertBST(root);

        inorderPrint(newRoot);
    }

    static void inorderPrint(TreeNode node) {
        if (node == null) return;
        inorderPrint(node.left);
        System.out.print(node.val + " ");
        inorderPrint(node.right);
    }
}

Line Notes

int accSum = 0;Initialize accumulated sum before traversal

convertBST(root.right);Traverse right subtree first to visit larger values

accSum += root.val;Add current node's value to accumulated sum

root.val = accSum;Update node's value to accumulated sum

convertBST(root.left);Traverse left subtree after updating current node

#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:
    int accSum = 0;

    TreeNode* convertBST(TreeNode* root) {
        if (root) {
            convertBST(root->right);
            accSum += root->val;
            root->val = accSum;
            convertBST(root->left);
        }
        return root;
    }
};

void inorderPrint(TreeNode* root) {
    if (!root) return;
    inorderPrint(root->left);
    cout << root->val << " ";
    inorderPrint(root->right);
}

int main() {
    TreeNode* root = new TreeNode(4);
    root->left = new TreeNode(1);
    root->right = new TreeNode(6);
    root->left->left = new TreeNode(0);
    root->left->right = new TreeNode(2);
    root->left->right->right = new TreeNode(3);
    root->right->left = new TreeNode(5);
    root->right->right = new TreeNode(7);
    root->right->right->right = new TreeNode(8);

    Solution sol;
    TreeNode* newRoot = sol.convertBST(root);
    inorderPrint(newRoot);
    cout << endl;
    return 0;
}

Line Notes

int accSum = 0;Initialize accumulated sum before traversal

convertBST(root->right);Traverse right subtree first to visit larger values

accSum += root->val;Add current node's value to accumulated sum

root->val = accSum;Update node's value to accumulated sum

convertBST(root->left);Traverse left subtree after updating current node

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

class Solution {
    constructor() {
        this.accSum = 0;
    }

    convertBST(root) {
        if (root) {
            this.convertBST(root.right);
            this.accSum += root.val;
            root.val = this.accSum;
            this.convertBST(root.left);
        }
        return root;
    }
}

// Driver code
const root = new TreeNode(4,
    new TreeNode(1,
        new TreeNode(0),
        new TreeNode(2, null, new TreeNode(3))),
    new TreeNode(6,
        new TreeNode(5),
        new TreeNode(7, null, new TreeNode(8)))
);

const sol = new Solution();
const newRoot = sol.convertBST(root);

function inorder(node) {
    if (!node) return [];
    return [...inorder(node.left), node.val, ...inorder(node.right)];
}

console.log(inorder(newRoot));

Line Notes

class Solution {Defines a class to hold the accumulated sum state across recursive calls

this.accSum = 0;Initialize accumulated sum before traversal

this.convertBST(root.right);Traverse right subtree first to visit larger values

this.accSum += root.val;Add current node's value to accumulated sum

root.val = this.accSum;Update node's value to accumulated sum

this.convertBST(root.left);Traverse left subtree after updating current node

⏱

Complexity

TimeO(n)

SpaceO(h) where h is tree height due to recursion stack

Each node is visited once in reverse inorder traversal, so time is O(n). Space is O(h) due to recursion stack, where h is the height of the tree.

💡 For n=20 and a balanced tree, h ~ 5, so space is small and time is linear.

Interview Verdict: Accepted / Optimal for interview

This approach is efficient and elegant, demonstrating mastery of BST properties and traversal techniques.

🧠

Iterative Approach (Reverse Inorder Traversal Using Stack)

💡 This approach avoids recursion by using an explicit stack to perform reverse inorder traversal, useful when recursion depth is a concern.

Intuition

Use a stack to simulate reverse inorder traversal (right-root-left), accumulate sums iteratively, and update node values.

Algorithm

1. Initialize an empty stack and set current node to root.
2. While current node is not null or stack is not empty:
3. Traverse to the rightmost node, pushing nodes onto the stack.
4. Pop a node from the stack, add its value to accumulated sum, update node's value.
5. Move to the left child of the popped node.
6. Return the root of the updated tree.

💡 Managing the stack manually can be tricky but helps understand traversal order and state management.

</>

Code

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

def convertBST(root):
    acc_sum = 0
    stack = []
    node = root
    while stack or node:
        while node:
            stack.append(node)
            node = node.right
        node = stack.pop()
        acc_sum += node.val
        node.val = acc_sum
        node = node.left
    return root

# Driver code
if __name__ == '__main__':
    root = TreeNode(4,
                    TreeNode(1,
                             TreeNode(0),
                             TreeNode(2, None, TreeNode(3))),
                    TreeNode(6,
                             TreeNode(5),
                             TreeNode(7, None, TreeNode(8))))
    new_root = convertBST(root)

    def inorder(node):
        return inorder(node.left) + [node.val] + inorder(node.right) if node else []
    print(inorder(new_root))

Line Notes

acc_sum = 0Initialize accumulated sum before traversal

while stack or node:Continue until all nodes are processed

while node:Traverse to rightmost node pushing nodes onto stack

node = stack.pop()Process the node with next largest value

acc_sum += node.valAdd current node's value to accumulated sum

node.val = acc_sumUpdate node's value to accumulated sum

node = node.leftMove to left subtree after processing current node

import java.util.Stack;

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

public class Solution {
    public TreeNode convertBST(TreeNode root) {
        int accSum = 0;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.right;
            }
            node = stack.pop();
            accSum += node.val;
            node.val = accSum;
            node = node.left;
        }
        return root;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(1);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(2);
        root.left.right.right = new TreeNode(3);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(7);
        root.right.right.right = new TreeNode(8);

        Solution sol = new Solution();
        TreeNode newRoot = sol.convertBST(root);

        inorderPrint(newRoot);
    }

    static void inorderPrint(TreeNode node) {
        if (node == null) return;
        inorderPrint(node.left);
        System.out.print(node.val + " ");
        inorderPrint(node.right);
    }
}

Line Notes

Stack<TreeNode> stack = new Stack<>();Use stack to simulate recursion

while (!stack.isEmpty() || node != null)Process all nodes until stack empty and no current node

while (node != null)Traverse to rightmost node pushing nodes

node = stack.pop();Pop node with next largest value

accSum += node.val;Add current node's value to accumulated sum

node.val = accSum;Update node's value to accumulated sum

node = node.left;Move to left subtree after processing

#include <iostream>
#include <stack>
using namespace std;

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

TreeNode* convertBST(TreeNode* root) {
    int accSum = 0;
    stack<TreeNode*> stk;
    TreeNode* node = root;
    while (!stk.empty() || node) {
        while (node) {
            stk.push(node);
            node = node->right;
        }
        node = stk.top();
        stk.pop();
        accSum += node->val;
        node->val = accSum;
        node = node->left;
    }
    return root;
}

void inorderPrint(TreeNode* root) {
    if (!root) return;
    inorderPrint(root->left);
    cout << root->val << " ";
    inorderPrint(root->right);
}

int main() {
    TreeNode* root = new TreeNode(4);
    root->left = new TreeNode(1);
    root->right = new TreeNode(6);
    root->left->left = new TreeNode(0);
    root->left->right = new TreeNode(2);
    root->left->right->right = new TreeNode(3);
    root->right->left = new TreeNode(5);
    root->right->right = new TreeNode(7);
    root->right->right->right = new TreeNode(8);

    TreeNode* newRoot = convertBST(root);
    inorderPrint(newRoot);
    cout << endl;
    return 0;
}

Line Notes

stack<TreeNode*> stk;Stack to simulate recursion

while (!stk.empty() || node)Process all nodes until stack empty and no current node

while (node)Traverse to rightmost node pushing nodes

node = stk.top();Pop node with next largest value

accSum += node->val;Add current node's value to accumulated sum

node->val = accSum;Update node's value to accumulated sum

node = node->left;Move to left subtree after processing

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

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

// Driver code
const root = new TreeNode(4,
    new TreeNode(1,
        new TreeNode(0),
        new TreeNode(2, null, new TreeNode(3))),
    new TreeNode(6,
        new TreeNode(5),
        new TreeNode(7, null, new TreeNode(8)))
);

const newRoot = convertBST(root);

function inorder(node) {
    if (!node) return [];
    return [...inorder(node.left), node.val, ...inorder(node.right)];
}

console.log(inorder(newRoot));

Line Notes

const stack = [];Stack to simulate recursion

while (stack.length > 0 || node !== null)Process all nodes until stack empty and no current node

while (node !== null)Traverse to rightmost node pushing nodes

node = stack.pop();Pop node with next largest value

accSum += node.val;Add current node's value to accumulated sum

node.val = accSum;Update node's value to accumulated sum

node = node.left;Move to left subtree after processing

⏱

Complexity

TimeO(n)

SpaceO(h) where h is tree height due to explicit stack

Each node is visited once, so time is O(n). Space is O(h) due to stack usage, similar to recursion stack.

💡 For balanced trees with n=20, h ~ 5, so space usage is small and time is linear.

Interview Verdict: Accepted / Optimal iterative solution

This approach is preferred when recursion depth is a concern or iterative solutions are requested.

📊

All Approaches - One-Glance Tradeoffs

💡 The reverse inorder recursive approach is the best balance of simplicity and efficiency for most interviews.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(n) recursion stack	Yes (deep recursion)	N/A	Mention only - never code
2. Recursive Reverse Inorder	O(n)	O(h) recursion stack	Possible for very deep trees	N/A	Preferred solution to code
3. Iterative Reverse Inorder	O(n)	O(h) explicit stack	No	N/A	Good alternative if recursion is restricted

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and confirm BST properties.Step 2: Describe the brute force approach to show understanding of the problem.Step 3: Explain inefficiency and introduce reverse inorder traversal approach.Step 4: Implement recursive solution and discuss time/space complexity.Step 5: Optionally, present iterative solution to handle recursion limits.Step 6: Test with examples and edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Understanding of BST properties, ability to identify traversal order, recursion and iteration skills, and optimization from brute force to efficient solution.

Common Follow-ups

• How to handle very large trees without recursion? → Use iterative approach with stack.
• Can you do this in O(1) space? → Morris traversal can be used to achieve O(1) space.

💡 These follow-ups test deeper knowledge of tree traversal techniques and space optimization.

🔍

Pattern Recognition

When to Use

1) Problem involves BST transformation; 2) Need to accumulate values from nodes greater than current; 3) Requires traversal order respecting BST ordering; 4) Output is modified tree.

Signature Phrases

'convert BST to greater tree''sum of all keys greater than the current key'

NOT This Pattern When

Problems that require only inorder traversal or do not involve accumulation of greater values.

Similar Problems

Convert BST to Greater Tree II - similar accumulation but with duplicatesBinary Tree to Greater Sum Tree - similar concept but for binary treesRange Sum of BST - uses BST traversal to sum values in range

Practice

1. You are given a binary search tree and asked to find the kth smallest element efficiently without traversing the entire tree. Which approach best guarantees an optimal solution in terms of time and space complexity?

easy

A. Perform a full inorder traversal to collect all elements in a list, then return the kth element from the list.

B. Use an iterative inorder traversal with a stack, stopping as soon as the kth smallest element is found.

C. Apply a greedy approach by always moving to the left child until k steps are taken.

D. Use dynamic programming to store counts of nodes in subtrees and then navigate to the kth element.

Solution

1. Step 1: Understand the problem constraints

   We want to find the kth smallest element in a BST efficiently, avoiding unnecessary traversal.

2. Step 2: Evaluate approaches

   Full inorder traversal (A) is correct but not optimal since it traverses the entire tree. Greedy left moves (C) fail because the kth element may not be in the leftmost path. DP (D) is complex and not standard for this problem. Iterative inorder with early stopping (B) visits only needed nodes, achieving O(H + k) time and O(H) space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Iterative inorder with early stopping avoids full traversal [OK]

Hint: Early stopping in inorder traversal is optimal [OK]

Common Mistakes:

• Assuming full traversal is necessary
• Confusing greedy left moves with inorder traversal

2. You are given a binary tree where each node has a unique integer value. You need to find whether a given value exists in the tree efficiently by leveraging the tree's ordering properties. Which approach guarantees the fastest search in the worst case?

easy

A. Use the BST property to decide whether to search left or right subtree at each node, recursively or iteratively.

B. Perform a breadth-first search (BFS) to find the value level by level.

C. Traverse the entire tree recursively checking each node until the value is found.

D. Use dynamic programming to store previously searched subtrees to avoid repeated work.

Solution

1. Step 1: Understand the problem constraints

   The tree is a BST, so left subtree nodes are less than the node, right subtree nodes are greater.

2. Step 2: Identify the optimal search approach

   Using the BST property allows skipping half of the tree at each step, leading to O(h) time complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   BST property guides search direction efficiently [OK]

Hint: BST property enables directed search, not full traversal [OK]

Common Mistakes:

• Thinking BFS or full traversal is optimal for BST search

3. What is the average time complexity per call of next() in the Morris traversal based BST Iterator, assuming the BST has n nodes?

medium

A. O(1) amortized per next() call because each edge is visited at most twice.

B. O(n) per next() call because each call may traverse the entire tree.

C. O(h) per next() call where h is the tree height due to traversing left children.

D. O(log n) per next() call assuming a balanced BST and stack usage.

Solution

1. Step 1: Understand Morris traversal edge visits

   Each edge in the BST is visited at most twice: once to create a thread and once to remove it.

2. Step 2: Calculate amortized cost per next()

   Since total work is O(n) for n nodes, and there are n calls to next(), average cost per call is O(1) amortized.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Amortized O(1) per next() matches Morris traversal properties [OK]

Hint: Morris traversal visits edges twice total [OK]

Common Mistakes:

• Assuming worst-case O(n) per call
• Confusing with stack-based O(h)
• Ignoring amortized analysis

4. Consider the following buggy code snippet for converting a sorted array to a height-balanced BST. Which line contains the subtle bug that can cause infinite recursion or stack overflow?

medium

A. Line 5: left_child = self.helper(nums, left, mid - 1)

B. Line 3: mid = (left + right) // 2

C. Line 7: root.right = self.helper(nums, mid + 1, right)

D. Line 2: if left >= right: return None

Solution

1. Step 1: Understand base case condition

   The base case should be when left > right, not left >= right, to allow single-element subarrays.

2. Step 2: Consequence of incorrect base case

   Using left >= right causes the recursion to skip processing subarrays of size 1, leading to infinite recursion or missing nodes.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Base case must allow left == right to process single elements [OK]

Hint: Base case must be left > right, not left >= right [OK]

Common Mistakes:

• Incorrect base case causing infinite recursion
• Misplaced mid calculation

5. The following code attempts to validate a BST using inorder traversal. Which line contains a subtle bug that can cause incorrect results on some inputs?

medium

A. Line checking if node is null (if not node: return true)

B. Line updating prev[0] = node.val

C. Line comparing node.val < prev[0] instead of node.val <= prev[0]

D. Line calling inorder(node.left)

Solution

1. Step 1: Identify BST strict inequality

   BST requires node.val to be strictly greater than previous inorder value; using < instead of <= allows duplicates.

2. Step 2: Understand impact of bug

   Using node.val < prev[0] misses the case when node.val == prev[0], incorrectly allowing duplicates and invalid BSTs.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Strict inequality check is essential to reject duplicates [OK]

Hint: BST nodes must be strictly increasing in inorder traversal [OK]

Common Mistakes:

• Allowing duplicates by using < instead of <=
• Not resetting prev between calls
• Only comparing immediate children