Convert BST to Greater Tree

▶

Steps

setup

Initialize variables

Initialize the accumulated sum to 0, create an empty stack, and set the current node to the root (node with value 4).

💡 Setting up these variables is essential to start the iterative reverse inorder traversal and keep track of the sum of visited nodes.

Line:

acc_sum = 0
stack = []
node = root

💡 The algorithm will use the stack to simulate recursion and acc_sum to accumulate node values.

traverse

Traverse right subtree from root

Push the current node (4) onto the stack and move to its right child (6) to reach the rightmost node first.

💡 Pushing nodes onto the stack preserves the path so we can return to them after exploring right children.

Line:

while node:
    stack.append(node)
    node = node.right

💡 The traversal goes right first to process larger values before smaller ones.

traverse

Push right child (7) and move to its right child (8)

Push node 7 onto the stack and move to its right child 8, continuing to go as far right as possible.

💡 This ensures the traversal visits the largest values first, which is key to accumulating sums correctly.

Line:

while node:
    stack.append(node)
    node = node.right

💡 The stack now contains nodes 4, 6, and 7, preserving the path back up.

fill_cells

Process rightmost node (8)

Pop node 8 from the stack, add its value (8) to acc_sum (0), update node 8's value to 8, then move to its left child (null).

💡 Processing the rightmost node first sets the initial accumulated sum for the traversal.

Line:

node = stack.pop()
acc_sum += node.val
node.val = acc_sum
node = node.left

💡 Node 8's value is updated to 8, starting the accumulation from the largest value.

fill_cells

Back to node 7, process it

Pop node 7 from the stack, add its value (7) to acc_sum (8), update node 7's value to 15, then move to its left child (null).

💡 After processing right child, update current node and move left to continue reverse inorder.

Line:

node = stack.pop()
acc_sum += node.val
node.val = acc_sum
node = node.left

💡 Node 7's value becomes 15, reflecting sum of 8 + 7.

fill_cells

Back to node 6, process it

Pop node 6 from the stack, add its value (6) to acc_sum (15), update node 6's value to 21, then move to its left child (5).

💡 Process node 6 after its right subtree is done, then move left to continue traversal.

Line:

node = stack.pop()
acc_sum += node.val
node.val = acc_sum
node = node.left

💡 Node 6's value updated to 21, sum of 15 + 6.

traverse

Traverse left child of node 6 (node 5)

Move to node 5, push it onto the stack, and since it has no right child, prepare to process it.

💡 Moving left after processing a node continues the reverse inorder traversal.

Line:

while node:
    stack.append(node)
    node = node.right

💡 Node 5 is next to be processed as it is the left child of 6.

fill_cells

Process node 5

Pop node 5 from the stack, add its value (5) to acc_sum (21), update node 5's value to 26, then move to its left child (null).

💡 Processing node 5 updates the accumulated sum and prepares to move left if possible.

Line:

node = stack.pop()
acc_sum += node.val
node.val = acc_sum
node = node.left

💡 Node 5's value becomes 26, sum of 21 + 5.

fill_cells

Back to node 3, process it

Pop node 3 (originally 4) from the stack, add its value (4) to acc_sum (26), update node 3's value to 30, then move to its left child (1).

💡 After processing right subtree, update root node and move left to continue traversal.

Line:

node = stack.pop()
acc_sum += node.val
node.val = acc_sum
node = node.left

💡 Node 4's value updated to 30, sum of 26 + 4.

traverse

Traverse right subtree of node 1 (node 2)

Push node 1 onto the stack and move to its right child (2), then push node 2 and move to its right child (3).

💡 Continuing reverse inorder traversal on left subtree of root.

Line:

while node:
    stack.append(node)
    node = node.right

💡 Stack now contains nodes 1 and 2, preparing to process their right children first.

fill_cells

Process node 3

Pop node 3 from the stack, add its value (3) to acc_sum (30), update node 3's value to 33, then move to its left child (null).

💡 Process rightmost node in this subtree first to accumulate sums correctly.

Line:

node = stack.pop()
acc_sum += node.val
node.val = acc_sum
node = node.left

💡 Node 3's value updated to 33, sum of 30 + 3.

fill_cells

Back to node 2, process it

Pop node 2 from the stack, add its value (2) to acc_sum (33), update node 2's value to 35, then move to its left child (null).

💡 Process node 2 after its right subtree is done, then move left.

Line:

node = stack.pop()
acc_sum += node.val
node.val = acc_sum
node = node.left

💡 Node 2's value updated to 35, sum of 33 + 2.

traverse

Traverse left child of node 2 (node 0)

Move to node 0, push it onto the stack. Since it has no right child, prepare to process it.

💡 Moving left continues the reverse inorder traversal on the leftmost subtree.

Line:

while node:
    stack.append(node)
    node = node.right

💡 Node 0 is next to be processed as the left child of 1.

fill_cells

Process node 0

Pop node 0 from the stack, add its value (0) to acc_sum (35), update node 0's value to 35, then move to its left child (null).

💡 Process leftmost node last, updating its value with accumulated sum.

Line:

node = stack.pop()
acc_sum += node.val
node.val = acc_sum
node = node.left

💡 Node 0's value updated to 35, sum remains 35.

reconstruct

Traversal complete, return updated root

Stack is empty and current node is null, traversal is complete. Return the root node with updated values.

💡 Returning the root signals the end of the transformation process.

Line:

return root

💡 The BST has been transformed into a Greater Tree with updated node values.

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  # STEP 1
    stack = []   # STEP 1
    node = root  # STEP 1
    while stack or node:  # STEP 2
        while node:  # STEP 2
            stack.append(node)  # STEP 2
            node = node.right  # STEP 2
        node = stack.pop()  # STEP 4
        acc_sum += node.val  # STEP 4
        node.val = acc_sum  # STEP 4
        node = node.left  # STEP 5
    return root  # STEP 6

# 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))

📊

Convert BST to Greater Tree - Watch the Algorithm Execute, Step by Step

Watching this step-by-step traversal and update process reveals how the algorithm transforms the BST into a Greater Tree by leveraging the BST property and reverse inorder traversal.

Current node: 1

416025738

Current node: 7

416025738

Current node: 9

416025738

416025788

4160251588

Current node: 6

41210251588

Current node: 5

41210251588

412102651588

Current node: 2

3012102651588

Current node: 8

3012102651588

3012102651588

Current node: 4

30352102651588

Current node: 4

30352102651588

30362136352615338

30362136352615338

Return: 1

Key Takeaways

✓ Reverse inorder traversal (right-root-left) is key to accumulating sums from largest to smallest node values.

This traversal order ensures each node's new value includes all greater values, which is hard to see from code alone.

✓ Using a stack simulates recursion and preserves traversal state explicitly.

Watching the stack grow and shrink clarifies how the algorithm backtracks and processes nodes in correct order.

✓ Node values update immediately upon visiting, reflecting the running sum.

Seeing values change step-by-step helps understand how the accumulated sum affects each node.