DSA sheet · Trees · Binary Search Tree pattern

BST to Greater Tree

In this video the teacher changes every value in a BST to "itself plus everything bigger than it". She calls it an easy question, and it is, once you see the trick. She first builds a brute force from the fact that inorder of a BST is sorted (store the values, take sums from the right end, write them back). Then she asks why we need three passes and an extra array, and gets to the optimal answer: walk the tree in reverse inorder (right, root, left) and keep one running sum. The problem matters because "visit the nodes in sorted order, or in reverse sorted order" is a tool you will reuse in many BST questions.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Brute force: inorder array + sums from the right
• Part B · Optimal: reverse inorder with a running sum
• Part C · Revision page

Part 0 · Before starting

What is a tree node?

Each node holds a value, a link to its left child and a link to its right child. A missing child is None.

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

The BST rule

A binary search tree (BST) is a binary tree where, for every node, all values in its left subtree are smaller and all values in its right subtree are bigger. (A subtree is a node plus everything below it.) The rule covers every node below, not only the direct children.

        4
       / \
      1   6
       \
        3

        4
       / \
      1   6
       \
        7

In the second tree, 7 > 1, so it's fine as 1's right child. But it is inside 4's left subtree and 7 > 4, so the tree breaks the rule. LeetCode also promises all values are different.

Why inorder of a BST is sorted

Inorder = visit the left subtree, then the node, then the right subtree. At every node, the left part holds only smaller values and the right part only bigger ones, so the node is printed exactly between them. Since this is true at every level, the full output comes out in increasing order.

Flip it to right, node, left (the teacher calls it reverse inorder) and you get the same values in decreasing order. That is the key tool for Part B.

Suffix sum (the teacher says "prefix sum from the right")

For an array, the sum "from position i to the end" is called the suffix sum. You build it by walking from the last element to the first and adding as you go. Example: [1, 2, 3] → from the right: 3, 3+2 = 5, 5+1 = 6 → [6, 5, 3].

Part A · Brute force: inorder array + sums from the right

LeetCode 538 (same as LeetCode 1038)

1The question in simple words

You get the root of a BST. Replace every node's value with: its own value + the sum of all values in the tree that are bigger than it. Return the root. The shape of the tree does not change, only the numbers.

            4
         /     \
        1       6
       / \     / \
      0   2   5   7
           \       \
            3       8

            30
         /      \
       36        21
      /  \      /  \
    36    35  26    15
            \         \
             33        8

The teacher's two quick checks:

• 4 has bigger values 5, 6, 7, 8 → new value = 4 + 5 + 6 + 7 + 8 = 30.
• 7 has only 8 bigger → 7 + 8 = 15.
• 8 is the largest, nothing is bigger → stays 8.
• 0 is the smallest, so everything else is bigger → it becomes the sum of the whole tree, 36.

2What the constraints tell us

• Number of nodes: 0 to 10⁴ → 0 is allowed, so the root can be None. Our code must return None safely.
• n ≤ 10⁴ → stay under about 10⁸ operations to avoid TLE. Even O(n²) = 10⁸ is borderline. O(n) is very safe.
• Values: −10⁴ to 10⁴. This one matters here because we are adding values, and sums can grow. The teacher works out the worst case: the smallest node collects the sum of all 10⁴ nodes. Even if every value were 10⁴ (it can't be, BST values are distinct and the left ones must be smaller), the sum is 10⁴ × 10⁴ = 10⁸. A 32-bit int holds up to about 2 × 10⁹, so an int is enough, no long needed.

3Intuition

The phrase "all values bigger than me" sounds like we need the values in order. A BST gives us sorted order for free through inorder. So: write the values down in sorted order, and the "bigger than me" values are simply everything to my right in that list.

4Building the idea from the example

Inorder of the input tree:

The teacher fills the wanted row from the right end: 8 → 8; 7 → 7 + 8 = 15; 6 → 6 + 15 = 21; 5 → 5 + 21 = 26; 4 → 30; 3 → 33; 2 → 35; 1 → 36; 0 → 36.

Look at what's happening: each answer is its own value plus the answer just to its right. That's exactly the suffix sum. The answer is hidden in the sorted list itself.

Now we need to put these numbers back into the tree. If we do inorder again, we meet the nodes in the same order (0, 1, 2, …). So the i-th node we meet gets arr[i]:

• start i = 0;
• in the second inorder, at the moment where the first inorder saved the value into the array, we instead write arr[i] into the node and do i += 1.

Walk it: go left from 4 → 1 → 0 → left of 0 is None, come back. First node met is 0 → set it to arr[0] = 36, i = 1. Back to 1 → arr[1] = 36, i = 2. Then 1's right: 2 (its left is None) → arr[2] = 35. Then 3 → 33. And so on.

5Approach steps

1. Inorder traversal → store all values in arr (sorted).
2. Walk arr from the last index to the first, keeping a running total; set arr[i] = total.
3. Set self.i = 0. Inorder traversal again; at each node, set node.val = arr[self.i] and move self.i forward.
4. Return root.

6Code (Python)

class Solution:
    def convertBST(self, root):
        arr = []
        self.inorder(root, arr)                  # pass 1: sorted values

        total = 0
        for i in range(len(arr) - 1, -1, -1):    # pass 2: sums from the right
            total += arr[i]
            arr[i] = total

        self.i = 0
        self.update(root, arr)                   # pass 3: write back
        return root

    def inorder(self, node, arr):
        if node is None:
            return
        self.inorder(node.left, arr)
        arr.append(node.val)
        self.inorder(node.right, arr)

    def update(self, node, arr):
        if node is None:
            return
        self.update(node.left, arr)
        node.val = arr[self.i]                   # instead of saving, overwrite
        self.i += 1
        self.update(node.right, arr)

7Code line by line

8Dry run (hand table)

9Complexity & remember

• Time O(3n) = O(n): one pass to collect, one to sum, one to write back. Linear, so it's accepted.
• Space O(n): the array of n values, plus O(h) for the recursion stack (h = height). Since n ≥ h, we say O(n).

It's already linear, so why improve? The teacher asks: why pass over the data three times and keep an extra array at all? Can we do it in one pass with no array?

Part B · Optimal: reverse inorder with a running sum

The question and constraints (steps ① and ②) are the same as in Part A. What changes is the idea.

3Intuition: visit the big values first

In Part A, the suffix sums were built by walking the sorted list from the biggest value down. What if we walk the tree itself in that order? Then, when we reach any node, we have already seen every bigger value, and their total is in our hands.

Normal inorder goes left, node, right (small to big). Swap the sides: right, node, left visits the nodes from big to small. Keep one variable total. At each node: add its value to total, then write total into the node.

4Building the idea: why right first?

• Suppose we started on the left, at 0. To fill in 0 we need the sum of everything bigger, and we haven't seen any of it yet. Stuck.
• Go to the node that can finish its own answer by itself: the biggest node, 8. Nothing is bigger, so 8 = 0 + 8 = 8. Now total = 8.
• Back to its parent 7: total was 8, add 7 → 15. Write 15, total = 15.
• Back to 6: 15 + 6 = 21. Then 6's left child 5: 21 + 5 = 26.
• Back to the root 4: 26 + 4 = 30. Then the left side of 4, again right first: 2's right 3 → 33, 2 → 35, 1 → 36, 0 → 36.

The bigger values sit on the right, so that's where we must go first.

5Approach steps

1. Set self.total = 0.
2. Reverse inorder from the root: if the node is None, return.
3. Go to the right subtree first.
4. Add the node's value to total; set the node's value to total.
5. Go to the left subtree.
6. Return root.

6Code (Python)

class Solution:
    def convertBST(self, root):
        self.total = 0                           # running sum of bigger values
        self.reverseInorder(root)
        return root

    def reverseInorder(self, node):
        if node is None:
            return
        self.reverseInorder(node.right)          # bigger values first
        self.total += node.val                   # add myself
        node.val = self.total                    # me + everything bigger
        self.reverseInorder(node.left)           # then the smaller ones

7Code line by line

8Dry run using the call stack

1. rev(4) → go right → rev(6) → go right → rev(7) → go right → rev(8) → right is None, returns.
2. At 8: total = 0 + 8 = 8, node 8 → 8. Left is None. rev(8) leaves the stack.
3. At 7: total = 8 + 7 = 15, node → 15. Left None. Done.
4. At 6: total = 15 + 6 = 21. Go left → rev(5): right None; total = 21 + 5 = 26; left None.
5. At 4 (root): total = 26 + 4 = 30. Go left → rev(1) → right → rev(2) → right → rev(3).
6. At 3: total = 33. At 2: total = 35 (2's left is None).
7. At 1: total = 36. Go left → rev(0): total = 36 + 0 = 36.
8. Stack empties. Return the root, which now holds 30. Tree matches the output ✓

The visit order is the sorted list read backwards, which is why the teacher names it reverse inorder.

9Complexity & remember

• Time O(n): one traversal, each node once (instead of O(3n)).
• Space O(h): only the recursion stack; no array. For a balanced BST that's O(log n); for a skewed tree (a straight line) it's O(n).

Part C · Revision page

def inorder(n):
    return inorder(n.left) + [n.val] + inorder(n.right) if n else []

root = TreeNode(4,
        TreeNode(1, TreeNode(0), TreeNode(2, None, TreeNode(3))),
        TreeNode(6, TreeNode(5), TreeNode(7, None, TreeNode(8))))
s = Solution()
root = s.convertBST(root)
print(inorder(root))              # [36, 36, 35, 33, 30, 26, 21, 15, 8]
print(root.val)                   # 30
print(s.convertBST(None))         # None
print(s.convertBST(TreeNode(5)).val)   # 5

Based on this video: Convert BST to Greater Tree