⚡Flashcard Drill➔
NeetCode #466LC-538MediumTrees
← Back to All Problems

#466 · #538 · Convert BST to Greater Tree(把二叉搜索树转换为累加树)

📌 Problem Statement & Constraints

Given the root of a binary search tree, convert it to a greater sum tree: every node's new value is the sum of all values greater than or equal to the original value. Return the root. Constraints: the number of nodes is in [0, 10^4], -10^4 <= Node.val <= 10^4.

💡 Core Algorithmic Approaches

  1. Visit the nodes in descending order, which for a BST means a right-root-left traversal.
  2. Maintain a running total; at each node add its original value to the total and assign the total to the node.
  3. Because the traversal is descending, the running total at a node is exactly the sum of all values greater than or equal to it.
  4. This is the reverse of an in-order traversal and is O(n).

💻 Benchmark Python3 Implementation

class Solution:
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        self.total = 0

        def dfs(node: Optional[TreeNode]) -> None:
            if not node:
                return
            dfs(node.right)                # largest values first
            self.total += node.val         # accumulate
            node.val = self.total          # this node sees all values >= its own
            dfs(node.left)

        dfs(root)
        return root

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one traversal.
💾 Space Complexity
O(h) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Using a normal in-order traversal: it visits ascending, so the running total would be the sum of smaller values.
  • Reading node.val after assigning it: the original value must be added to the total before the assignment.
  • Resetting the total between subtrees: it must accumulate across the whole traversal.
  • Assuming values are non-negative: they can be negative, and the algorithm handles them.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems