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 a key. You need to remove the node with this key while maintaining the BST property. Which approach guarantees the correct and efficient deletion in all cases, including nodes with two children?

easy

A. Use a greedy approach that always deletes the node by replacing it with its left child, ignoring the right subtree.

B. Perform a breadth-first traversal to find and remove the node, then rebuild the tree from scratch.

C. Use a recursive approach that finds the node, then if it has two children, replace it with its in-order successor and recursively delete the successor.

D. Use dynamic programming to store subtrees and delete nodes based on precomputed results.

Solution

1. Step 1: Understand BST deletion cases

   Deletion must handle three cases: leaf node, node with one child, and node with two children. The two children case requires replacing the node with its in-order successor or predecessor to maintain BST properties.

2. Step 2: Identify approach that handles all cases correctly

   The recursive approach that finds the node, replaces it with its in-order successor if it has two children, and recursively deletes the successor ensures correctness and efficiency.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Only Use a recursive approach that finds the node, then if it has two children, replace it with its in-order successor and recursively delete the successor. correctly handles all deletion cases preserving BST [OK]

Hint: Two-children deletion requires successor replacement [OK]

Common Mistakes:

• Greedy deletion ignoring right subtree breaks BST
• Rebuilding tree is inefficient
• Dynamic programming irrelevant here

2. You are given a binary search tree and two nodes within it. You need to find the node that is the deepest ancestor common to both nodes, leveraging the BST property to optimize the search. Which approach guarantees the most efficient solution?

easy

A. Perform two separate DFS traversals to find paths from root to each node, then compare paths to find the last common node.

B. Apply dynamic programming to store ancestors of each node and then find the lowest common ancestor by comparing stored data.

C. Iteratively traverse the BST from the root, moving left or right depending on the values of the two nodes relative to the current node, stopping when the current node splits the paths to the two nodes.

D. Use a greedy approach that always moves towards the node with the smaller value until both nodes are found.

Solution

1. Step 1: Understand BST property usage

   In a BST, left subtree nodes are smaller and right subtree nodes are larger than the current node. This allows pruning the search space efficiently.

2. Step 2: Identify optimal traversal

   Starting from root, if both target nodes are smaller, go left; if both are larger, go right; else current node is the split point and thus the LCA.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Iterative BST traversal uses O(h) time and O(1) space [OK]

Hint: Use BST property to prune search paths [OK]

Common Mistakes:

• Using path comparison wastes time and space
• Greedy approach ignores split point logic
• Dynamic programming is unnecessary overhead

3. Given the following code for trimming a BST and the input tree with root value 3, left child 1, right child 4, and low=2, high=3, what is the value of the root node after trimming?

easy

A. 2

B. 3

C. 1

D. 4

Solution

1. Step 1: Move root to valid range

   Root=3 is within [2,3], so no change.

2. Step 2: Trim left subtree

   Left child=1 < 2, so replace left child with its right subtree (None). Left child becomes None.

3. Step 3: Trim right subtree

   Right child=4 > 3, so replace right child with its left subtree (None). Right child becomes None.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Root remains 3 with no children after trimming [OK]

Hint: Check root adjustment before subtree trimming [OK]

Common Mistakes:

• Assuming root changes when already in range
• Forgetting to trim subtrees correctly

4. Consider the following buggy code for trimming a BST. Which line contains the subtle bug that can cause the resulting tree to violate BST properties or cause runtime errors?

medium

A. Line 3: root = root.left when root.val < low

B. Line 5: root = root.left when root.val > high

C. Line 10: cur.left = cur.left.right inside left subtree trimming

D. Line 16: cur.right = cur.right.left inside right subtree trimming

Solution

1. Step 1: Check root adjustment logic

   If root.val < low, root should move to root.right, not root.left, to find valid nodes.

2. Step 2: Verify other lines

   Line 5 correctly moves root to root.left if root.val > high. Lines 10 and 16 correctly adjust subtree pointers.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incorrect pointer move causes invalid pruning or infinite loop [OK]

Hint: Root moves wrong direction when value < low [OK]

Common Mistakes:

• Confusing left and right subtree moves
• Incorrect pointer updates causing invalid BST

5. Suppose the BST can contain duplicate values, and you want to find the lowest common ancestor of two nodes p and q that may have the same value. Which modification to the optimal iterative algorithm correctly handles duplicates while maintaining efficiency?

hard

A. Define a consistent rule that duplicates go to the right subtree and use original algorithm without changes.

B. Modify comparisons to use '<=' and '>=' to ensure traversal includes duplicates on both sides.

C. Augment each node with a count of duplicates and traverse left or right based on counts to find LCA.

D. Store paths from root to p and q and compare them to find LCA, since BST property is ambiguous with duplicates.

Solution

1. Step 1: Understand duplicate handling in BST

   BSTs with duplicates require a consistent insertion rule, commonly duplicates go to right subtree.

2. Step 2: Modify comparisons to include duplicates

   Using '<=' and '>=' in comparisons ensures traversal includes duplicates correctly on both sides.

3. Step 3: Avoid ambiguous or inefficient methods

   Path comparison or augmenting nodes adds overhead and complexity.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Inclusive comparisons handle duplicates while preserving efficiency [OK]

Hint: Modify comparison operators to handle duplicates correctly [OK]

Common Mistakes:

• Using strict comparisons that miss duplicates
• Reverting to path comparison losing efficiency
• Adding unnecessary data structures