Range Sum of BST

▶

Steps

setup

Initialize stack with root node

Start by placing the root node (value 10) on the stack and initialize the total sum to 0.

💡 This sets up the traversal starting point and prepares to accumulate the sum.

Line:

stack = [root]
total = 0

💡 The stack holds nodes to visit; starting with root ensures full tree coverage.

traverse

Pop node 10 from stack

Pop the top node (value 10) from the stack to process it.

💡 Processing nodes one by one allows checking their values against the range.

Line:

node = stack.pop()

💡 The current node to evaluate is 10, the root.

compare

Node 10 is within range, add to sum and push children

Since 10 is between 7 and 15, add 10 to total and push its left (5) and right (15) children onto the stack.

💡 Nodes in range contribute to the sum and their children might also be in range.

Line:

if low <= node.val <= high:
    total += node.val
    stack.append(node.left)
    stack.append(node.right)

💡 Adding node 10 to sum and exploring both children ensures all possible in-range nodes are checked.

traverse

Pop node 15 from stack

Pop the top node (value 15) from the stack to process it next.

💡 The stack is LIFO, so the last pushed node (15) is processed before 5.

Line:

node = stack.pop()

💡 Node 15 is the next candidate for range checking.

compare

Node 15 is within range, add to sum and push children

Since 15 is between 7 and 15, add 15 to total and push its left (null) and right (18) children onto the stack.

💡 Nodes in range add to sum and their children might also be relevant.

Line:

if low <= node.val <= high:
    total += node.val
    stack.append(node.left)
    stack.append(node.right)

💡 Adding 15 to sum and exploring children ensures no in-range nodes are missed.

traverse

Pop node 5 from stack

Pop the top node (value 5) from the stack to process it next.

💡 Next node to evaluate is 5, which is less than the low bound.

Line:

node = stack.pop()

💡 Node 5 will be checked against the range to decide pruning.

compare

Node 5 is less than low, push only right child

Since 5 is less than 7, skip left child and push only right child (7) onto the stack.

💡 Pruning left subtree avoids unnecessary checks since all left nodes are smaller.

Line:

elif node.val < low:
    stack.append(node.right)

💡 BST property allows skipping left subtree when node value is below low.

traverse

Pop node 7 from stack

Pop the top node (value 7) from the stack to process it next.

💡 Node 7 is exactly the low bound, so it will be checked for inclusion.

Line:

node = stack.pop()

💡 Node 7 is the next candidate for range checking.

compare

Node 7 is within range, add to sum and push children

Since 7 is between 7 and 15, add 7 to total and push its left and right children (both null) onto the stack.

💡 Leaf nodes in range add to sum but have no children to explore.

Line:

if low <= node.val <= high:
    total += node.val
    stack.append(node.left)
    stack.append(node.right)

💡 Adding 7 completes the sum of all in-range nodes found so far.

traverse

Pop null from stack and skip

Pop a null node from the stack and skip processing since it does not exist.

💡 Null nodes represent absent children and do not affect the sum or traversal.

Line:

if node:
    ...
else:
    continue

💡 Skipping null nodes prevents errors and unnecessary processing.

traverse

Pop null from stack and skip

Pop another null node from the stack and skip processing.

💡 Multiple null nodes appear as children of leaf nodes and are ignored.

Line:

if node:
    ...
else:
    continue

💡 Null nodes mark ends of branches.

traverse

Pop node 18 from stack

Pop node 18 from the stack to process it next.

💡 Node 18 is greater than the high bound and will be pruned accordingly.

Line:

node = stack.pop()

💡 Node 18 will be checked against the range to decide pruning.

compare

Node 18 is greater than high, push only left child

Since 18 is greater than 15, skip right child and push only left child (null) onto the stack.

💡 Pruning right subtree avoids unnecessary checks since all right nodes are larger.

Line:

else:  # node.val > high
    stack.append(node.left)

💡 BST property allows skipping right subtree when node value is above high.

traverse

Pop null from stack and skip

Pop a null node from the stack and skip processing.

💡 Null nodes mark ends of branches and are ignored.

Line:

if node:
    ...
else:
    continue

💡 Skipping null nodes prevents errors and unnecessary processing.

traverse

Pop null from stack and skip

Pop the last null node from the stack and skip processing.

💡 All nodes have been processed or pruned; traversal is about to end.

Line:

if node:
    ...
else:
    continue

💡 Traversal ends when stack is empty.

reconstruct

Traversal complete, return total sum

Stack is empty, traversal is complete. Return the total sum of nodes within range.

💡 The final sum is the answer to the problem.

Line:

return total

💡 The sum 32 includes all nodes with values 7, 10, and 15.

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

def rangeSumBST(root, low, high):
    stack = [root]  # STEP 1
    total = 0       # STEP 1
    while stack:    # STEP 2 loop start
        node = stack.pop()  # STEP 2
        if node:            # STEP 3
            if low <= node.val <= high:  # STEP 4
                total += node.val       # STEP 4
                stack.append(node.left) # STEP 4
                stack.append(node.right)# STEP 4
            elif node.val < low:         # STEP 5
                stack.append(node.right)# STEP 5
            else:  # node.val > high    # STEP 6
                stack.append(node.left) # STEP 6
    return total  # STEP 16

if __name__ == '__main__':
    root = TreeNode(10, TreeNode(5, TreeNode(3), TreeNode(7)), TreeNode(15, None, TreeNode(18)))
    print(rangeSumBST(root, 7, 15))  # Output: 32

📊

Range Sum of BST - Watch the Algorithm Execute, Step by Step

Watching this step-by-step traversal reveals how BST properties help skip unnecessary nodes, making the algorithm efficient and intuitive.

105153718

Current node: 0

105153718

105153718

Current node: 2

105153718

105153718

Current node: 1

105153718

105153718

Current node: 4

105153718

105153718

105153718

105153718

Current node: 5

105153718

105153718

105153718

105153718

105153718

Return: 32

Key Takeaways

✓ BST properties allow pruning subtrees that cannot contain values in the range, improving efficiency.

This pruning is not obvious from code alone but is clear when watching which nodes are skipped.

✓ The iterative DFS with a stack simulates recursion and shows explicit control over traversal order.

Seeing the stack contents change step-by-step helps understand traversal mechanics.

✓ Only nodes within the range contribute to the sum, and their children are explored; nodes outside the range prune one subtree.

This decision logic is clearer when watching each node's value compared to the range.

Practice

1. Consider the following buggy code snippet for converting a sorted array to a height-balanced BST. Which line contains the subtle bug that can cause infinite recursion or stack overflow?

medium

A. Line 5: left_child = self.helper(nums, left, mid - 1)

B. Line 3: mid = (left + right) // 2

C. Line 7: root.right = self.helper(nums, mid + 1, right)

D. Line 2: if left >= right: return None

Solution

1. Step 1: Understand base case condition

   The base case should be when left > right, not left >= right, to allow single-element subarrays.

2. Step 2: Consequence of incorrect base case

   Using left >= right causes the recursion to skip processing subarrays of size 1, leading to infinite recursion or missing nodes.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Base case must allow left == right to process single elements [OK]

Hint: Base case must be left > right, not left >= right [OK]

Common Mistakes:

• Incorrect base case causing infinite recursion
• Misplaced mid calculation

2. Consider the following buggy code snippet for finding the kth smallest element in a BST. Which line contains the subtle bug that can cause incorrect results or runtime errors?

def kthSmallest(root: Optional[TreeNode], k: int) -> int:
    stack = []
    current = root
    count = 0

    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        count += 1
        if count == k:
            return current.val
        current = current.right

# Bug introduced: k is used as zero-based index (count == k-1) instead of one-based

medium

A. Line with 'if count == k - 1:'

B. Line with 'count += 1'

C. Line with 'stack.append(current)'

D. Line with 'current = current.right'

Solution

1. Step 1: Identify the off-by-one bug

   The condition uses 'count == k - 1' which treats k as zero-based, but k is one-based in problem definition.

2. Step 2: Consequence of bug

   This causes the function to return the (k-1)th smallest element or miss the kth element, leading to incorrect results or runtime errors if k=1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct condition must be 'count == k' to match one-based indexing [OK]

Hint: Check indexing base for k carefully [OK]

Common Mistakes:

• Using zero-based index for k
• Misplacing count increment
• Returning too early

3. The following code attempts to search for a value in a BST. Identify the line containing the subtle bug that can cause incorrect behavior or inefficiency.

def searchBST(root, val):
    if root is None:
        return None
    if root.val == val:
        return root
    left_search = searchBST(root.left, val)
    if left_search is not None:
        return left_search
    return searchBST(root.right, val)

medium

A. Line 5: left_search = searchBST(root.left, val)

B. Line 4: if root.val == val: return root

C. Line 2: if root is None: return None

D. Line 7: return searchBST(root.right, val)

Solution

1. Step 1: Understand the code logic

   This code searches both left and right subtrees regardless of BST property.

2. Step 2: Identify inefficiency bug

   Line 5 always searches left subtree even if val > root.val, ignoring BST property and causing O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Ignoring BST property causes unnecessary subtree searches [OK]

Hint: Searching both subtrees ignores BST property [OK]

Common Mistakes:

• Not pruning search using BST property

4. Suppose the input array can contain duplicate values and you want to build a height-balanced BST that allows duplicates on the right subtree. Which modification to the optimal approach is correct?

hard

A. Change mid calculation to always pick the left middle element to ensure duplicates go to the right subtree.

B. Change the recursive calls to insert duplicates always into the left subtree to maintain balance.

C. Keep mid calculation as is, but when inserting duplicates, always place them in the right subtree during tree construction.

D. Use the brute force approach inserting elements one by one to handle duplicates correctly.

Solution

1. Step 1: Understand duplicate handling

   Duplicates should be consistently placed in the right subtree to maintain BST property.

2. Step 2: Modify insertion logic

   Keep mid calculation unchanged for balance; during node creation, ensure duplicates go to right subtree by design.

3. Step 3: Avoid brute force

   Brute force insertion leads to unbalanced trees and higher complexity.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Maintain balance and BST property by consistent duplicate placement right [OK]

Hint: Keep mid; place duplicates right during construction [OK]

Common Mistakes:

• Changing mid breaks balance
• Inserting duplicates left breaks BST property

5. Suppose the problem is extended so that multiple pairs of nodes (more than two nodes) are swapped in the BST, possibly non-adjacent. Which of the following modifications to the recovery algorithm is correct and efficient?

hard

A. Use the Morris inorder traversal to detect all violations and store all nodes involved, then sort their values and reassign in inorder traversal.

B. Run the Morris traversal multiple times, each time swapping the first detected violation nodes until no violations remain.

C. Use the brute force approach: inorder traversal to collect all values, sort them, then overwrite the tree nodes in inorder traversal.

D. Modify the Morris traversal to swap nodes immediately upon detecting each violation without storing nodes, fixing all swaps in one pass.

Solution

1. Step 1: Understand the problem extension

   Multiple pairs of nodes swapped means multiple violations, possibly complex to detect and fix in one pass.

2. Step 2: Evaluate approaches

   Morris traversal detects only two nodes swapped optimally; multiple swaps require collecting all values, sorting, and rewriting nodes, which brute force does efficiently.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Brute force approach handles multiple swaps correctly by sorting all values [OK]

Hint: Multiple swaps require full value sorting and rewriting [OK]

Common Mistakes:

• Assuming Morris traversal can fix multiple swaps in one pass
• Trying to swap nodes immediately without full detection
• Running multiple passes of Morris traversal inefficiently