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 need to design an iterator over a binary search tree that returns elements in ascending order, but you want to avoid storing all elements upfront to save space. Which approach best fits this requirement?

easy

A. Use a divide-and-conquer approach to merge sorted lists from left and right subtrees at each next() call.

B. Perform a full inorder traversal upfront and store all elements in a list for O(1) next() calls.

C. Use a breadth-first traversal to visit nodes level by level and return elements in sorted order.

D. Use a controlled inorder traversal with a stack to lazily fetch the next smallest element on demand.

Solution

1. Step 1: Understand the problem constraints

   The iterator must return elements in ascending order without storing all nodes upfront to save space.

2. Step 2: Evaluate approaches

   Full inorder traversal (B) uses O(n) space upfront, breadth-first (C) does not guarantee sorted order, and divide-and-conquer merging (D) is inefficient per next() call. Controlled inorder traversal with a stack (A) lazily fetches the next smallest element using O(h) space, which is optimal for this problem.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Lazy stack-based inorder traversal matches the problem requirements [OK]

Hint: Lazy stack traversal avoids full storage [OK]

Common Mistakes:

• Thinking BFS returns sorted order
• Assuming full traversal is always best
• Confusing divide-and-conquer with lazy iteration

2. Given the following code snippet for converting a sorted array to a height-balanced BST, what is the value of the root node's value after the first call to helper with input nums = [1, 3, 5]?

easy

A. 3

B. 1

C. 5

D. None

Solution

1. Step 1: Calculate mid index for initial call

   For nums=[1,3,5], left=0, right=2, mid=(0+2)//2=1.

2. Step 2: Identify root value

   nums[mid] = nums[1] = 3, so root node value is 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mid index calculation picks 3 as root [OK]

Hint: Mid index picks middle element as root [OK]

Common Mistakes:

• Choosing first or last element as root
• Off-by-one mid calculation

3. You are given a binary search tree and two nodes within it. You need to find the node that is the deepest ancestor common to both nodes, leveraging the BST property to optimize the search. Which approach guarantees the most efficient solution?

easy

A. Perform two separate DFS traversals to find paths from root to each node, then compare paths to find the last common node.

B. Apply dynamic programming to store ancestors of each node and then find the lowest common ancestor by comparing stored data.

C. Iteratively traverse the BST from the root, moving left or right depending on the values of the two nodes relative to the current node, stopping when the current node splits the paths to the two nodes.

D. Use a greedy approach that always moves towards the node with the smaller value until both nodes are found.

Solution

1. Step 1: Understand BST property usage

   In a BST, left subtree nodes are smaller and right subtree nodes are larger than the current node. This allows pruning the search space efficiently.

2. Step 2: Identify optimal traversal

   Starting from root, if both target nodes are smaller, go left; if both are larger, go right; else current node is the split point and thus the LCA.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Iterative BST traversal uses O(h) time and O(1) space [OK]

Hint: Use BST property to prune search paths [OK]

Common Mistakes:

• Using path comparison wastes time and space
• Greedy approach ignores split point logic
• Dynamic programming is unnecessary overhead

4. What is the worst-case time complexity of the optimal iterative BST search algorithm when searching for a value in a BST with n nodes and height h?

medium

A. O(log n) always because BSTs are balanced.

B. O(n) because you might have to visit every node in the tree.

C. O(h) because the search path follows the height of the tree.

D. O(1) because the search uses direct indexing.

Solution

1. Step 1: Understand BST height and search path

   The search path length is at most the height h of the BST, as each step moves down one level.

2. Step 2: Analyze worst-case time complexity

   In worst case (unbalanced tree), h can be up to n, but complexity is expressed as O(h), not O(n) directly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Search complexity depends on tree height, not total nodes necessarily [OK]

Hint: Time depends on tree height, not total nodes always [OK]

Common Mistakes:

• Assuming O(log n) always, ignoring unbalanced trees

5. Suppose the BST can contain duplicate values and you want to find if there exist two nodes (not necessarily distinct) whose values sum to k. Which modification to the optimal inorder + two-pointer approach correctly handles this scenario?

hard

A. Perform inorder traversal and remove duplicates before applying two-pointer technique.

B. Use the same two-pointer approach but allow left and right pointers to point to the same index.

C. Use a hash set to store values and check complements, ignoring duplicates.

D. During two-pointer traversal, if left == right, check if the value at that index appears at least twice in the BST.

Solution

1. Step 1: Understand duplicates and two-pointer constraints

   Two-pointer approach requires two distinct indices; if pointers meet, need to verify if duplicate values exist.

2. Step 2: Modify check when left == right

   Check if the value at that index occurs at least twice in the BST to allow sum with itself.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Only During two-pointer traversal, if left == right, check if the value at that index appears at least twice in the BST. correctly handles duplicates without breaking two-pointer logic [OK]

Hint: Check duplicates count when pointers meet [OK]

Common Mistakes:

• Allowing pointers to be equal without duplicate check
• Removing duplicates loses valid pairs
• Ignoring duplicates in hash set approach