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.

Practice

1. You are given a binary search tree and a target integer k. You need to determine if there exist two distinct nodes in the BST whose values sum up to k. Which of the following approaches guarantees an optimal solution in terms of time and space complexity?

easy

A. Perform an inorder traversal to get a sorted array, then use two pointers to find if a pair sums to k.

B. Use dynamic programming to store sums of all subtree pairs and check for k.

C. Perform a brute force nested traversal of all node pairs directly on the BST without extra storage.

D. Use a greedy approach by always choosing the smallest and largest node values and adjusting pointers.

Solution

1. Step 1: Understand BST property and inorder traversal

   Inorder traversal of a BST produces a sorted array of node values.

2. Step 2: Apply two-pointer technique on sorted array

   Using two pointers at start and end, we can efficiently find if two values sum to k in O(n) time and O(n) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Inorder + two pointers is optimal and uses BST ordering [OK]

Hint: Inorder traversal yields sorted array for two-pointer sum [OK]

Common Mistakes:

• Trying nested loops directly on BST nodes without flattening
• Assuming greedy approach works without sorting
• Using DP which is unnecessary here

2. Consider the following buggy code for inserting a value into a BST. Which line contains the subtle bug that causes the insertion to fail silently in some cases?

def insertIntoBST(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        insertIntoBST(root.left, val)
    else:
        insertIntoBST(root.right, val)
    return root

medium

A. Line 2: if root is None

B. Line 4: if val < root.val

C. Line 7: insertIntoBST(root.right, val)

D. Line 5: insertIntoBST(root.left, val)

Solution

1. Step 1: Analyze recursive calls

   Recursive calls to insertIntoBST on root.left or root.right do not update the parent's child pointer.

2. Step 2: Identify missing assignment

   Lines 5 and 7 call insertIntoBST but do not assign the returned subtree back to root.left or root.right, so insertion is lost.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing assignment causes silent insertion failure [OK]

Hint: Recursive insert must assign returned subtree to parent's child [OK]

Common Mistakes:

• Not updating parent's child pointer
• Confusing base case with recursive step
• Incorrect comparison operator

3. Suppose you want to extend the BST Iterator to support repeated calls to next() that return the same element multiple times (i.e., allow reuse of elements). Which modification to the Morris traversal based iterator is correct?

hard

A. Remove thread restoration to keep the tree threaded and allow repeated visits to the same node.

B. Store all elements in a list during initialization to allow repeated next() calls without traversal.

C. Modify _advance() to not move current pointer after returning next_val, so next() returns same value again.

D. Use a stack-based iterator and push nodes multiple times to simulate repeated next() calls.

Solution

1. Step 1: Understand reuse requirement

   Allowing repeated next() calls to return the same element requires storing elements since Morris traversal advances and loses previous state.

2. Step 2: Evaluate modifications

   Removing thread restoration (A) corrupts tree, modifying _advance() to not move current (C) breaks traversal logic, and pushing nodes multiple times on stack (B) is inefficient and incorrect. Storing all elements upfront (D) enables repeated next() calls reliably.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Pre-storing elements supports repeated next() calls without traversal [OK]

Hint: Reuse requires storing elements, not traversal tricks [OK]

Common Mistakes:

• Assuming traversal can be paused and repeated
• Ignoring tree corruption from missing restoration
• Trying to simulate reuse with threads

4. Suppose the BST can contain duplicate values, and you want to find all nodes with a given value. Which modification to the optimal iterative search algorithm correctly finds all such nodes?

hard

A. Stop at the first found node and return it, since duplicates are not allowed in BSTs.

B. Modify the search to continue searching both left and right subtrees even after finding a matching node.

C. Traverse the entire tree recursively to collect all nodes with the target value, ignoring BST property.

D. Use a queue to perform BFS and collect all nodes with the target value efficiently.

Solution

1. Step 1: Understand duplicates in BST

   Duplicates can appear on either left or right subtree depending on BST definition.

2. Step 2: Modify search to find all matches

   After finding a node with val, continue searching both subtrees to find all duplicates.

3. Step 3: Avoid full traversal

   Using BST property to prune search still possible by checking subtrees where duplicates may exist.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Continuing search after first match finds all duplicates [OK]

Hint: Duplicates require searching both subtrees after match [OK]

Common Mistakes:

• Stopping at first match or ignoring BST property completely

5. Suppose the BST can contain duplicate values and the range is inclusive [low, high]. How should the trimming algorithm be modified to correctly handle duplicates without breaking BST properties?

hard

A. Change all comparisons to strict inequalities (e.g., < low to <= low) to exclude duplicates outside range.

B. Rebuild the BST from scratch after filtering duplicates to ensure correct ordering.

C. Adjust pruning conditions to include nodes equal to low or high by using <= and >= comparisons appropriately.

D. Ignore duplicates during pruning since BST properties guarantee uniqueness.

Solution

1. Step 1: Understand duplicates in BST

   Duplicates can be on left or right subtree depending on implementation; inclusive range means nodes equal to low or high must be kept.

2. Step 2: Modify pruning conditions

   Use <= and >= in comparisons to keep nodes equal to boundaries, ensuring duplicates within range remain.

3. Step 3: Avoid rebuilding

   Rebuilding wastes time and space; pruning with adjusted conditions preserves BST and duplicates correctly.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Inclusive pruning keeps duplicates at boundaries [OK]

Hint: Use inclusive comparisons to keep duplicates within range [OK]

Common Mistakes:

• Using strict inequalities excludes boundary duplicates
• Rebuilding unnecessarily wastes resources