Convert BST to Greater Tree
Given the root of a BST, convert it to a Greater Tree such that every key is changed to the original key plus the sum of all other keys greater than the original key. Use reverse in-order traversal.
Why Interviewers Ask This
Google interviewers ask this to evaluate a candidate's ability to optimize standard tree traversals. They specifically look for the insight that reverse in-order traversal allows calculating cumulative sums in a single pass without extra space, testing deep understanding of BST properties and algorithmic efficiency over brute-force solutions.
How to Answer This Question
1. Clarify requirements: Confirm that 'greater' means strictly larger keys and that the transformation happens in-place. 2. Analyze the property: Explain that an in-order traversal visits nodes in ascending order, so a reverse in-order (Right-Root-Left) visits them descending. 3. Propose the strategy: Describe maintaining a running sum variable initialized to zero. As you visit each node, add its value to the sum, update the node with this new sum, then proceed to the left child. 4. Discuss complexity: Explicitly state that time complexity is O(N) since every node is visited once, and space complexity is O(H) due to recursion stack depth, where H is the tree height. 5. Validate edge cases: Briefly mention handling null roots or single-node trees to show thoroughness before writing code.
Key Points to Cover
- Identifying that reverse in-order traversal naturally provides the required descending sequence
- Using a single running sum variable to avoid nested loops or multiple passes
- Achieving O(N) time complexity by visiting each node exactly once
- Demonstrating awareness of O(H) space complexity relative to recursion depth
- Explaining the logic clearly before implementing the recursive solution
Sample Answer
To solve the Convert BST to Greater Tree problem efficiently, I would leverage the unique properties of Binary Search Trees. First, I need to understand that we want each node to store its original value plus the sum of all values greater than it. A standard in-order traversal gives us sorted ascending values, but we need the opposite direction. Therefore, I will use a reverse in-order traversal, visiting the right subtree, then the current node, and finally the left subtree. This ensures we process nodes from largest to smallest. I'll maintain a global or passed reference variable called 'runningSum', initialized to zero. When I visit a node, I first recursively process its right child. Once that returns, I add the current node's value to 'runningSum'. Then, I update the current node's value to this new 'runningSum'. Finally, I recurse on the left child. For example, if the tree has nodes 5, 2, and 13, processing 13 sets the sum to 13. Processing 5 adds 5 to get 18, updating 5 to 18. Processing 2 adds 2 to get 20, updating 2 to 20. This approach achieves O(N) time complexity because we touch each node exactly once, and O(H) space complexity for the call stack, which is optimal for this structure. This method aligns well with Google's expectation for clean, efficient, and logically sound algorithms.
Common Mistakes to Avoid
- Attempting to find the maximum node repeatedly for every node, leading to inefficient O(N^2) complexity
- Forgetting to update the running sum before assigning it to the current node's value
- Confusing the order of operations by processing the left child before the right child
- Neglecting to handle the base case where the root or children are null
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.
Related Interview Questions
Find K Closest Elements (Heaps)
Medium
MetaEvaluate Reverse Polish Notation (Stack)
Medium
SpotifyConvert Binary Tree to Doubly Linked List in Place
Hard
MicrosoftDesign a Set with $O(1)$ `insert`, `remove`, and `check`
Easy
CiscoDefining Your Own Success Metrics
Medium
GoogleProduct Strategy: Addressing Market Saturation
Medium
Google