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 Python code implementing the Morris inorder traversal to recover a BST with two swapped nodes. Given the input tree with nodes [3,1,4,null,null,2] where nodes 2 and 3 are swapped, what is the value of the variable second.val after the traversal completes?

easy

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Trace inorder traversal with Morris method

   The inorder traversal visits nodes in order: 1, 3, 2, 4. The violations are detected when prev.val > current.val: first at (3,2).

2. Step 2: Identify swapped nodes

   First violation sets first=3, second=2. No second violation occurs, so second remains 2.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Second node detected is the node with value 2 [OK]

Hint: Second swapped node is the smaller value in violation [OK]

Common Mistakes:

• Confusing first and second nodes
• Missing second violation for adjacent swaps
• Off-by-one in traversal order

2. You are given a binary tree and need to determine if it satisfies the property that for every node, all nodes in its left subtree have smaller values and all nodes in its right subtree have larger values, with no duplicates allowed. Which approach guarantees an optimal solution to this problem?

easy

A. Check each node by comparing it only with its immediate children recursively.

B. Apply a greedy algorithm that validates nodes as soon as they are visited.

C. Use dynamic programming to store subtree min and max values and combine results bottom-up.

D. Perform an inorder traversal and verify that the node values are strictly increasing.

Solution

1. Step 1: Understand BST property

   The BST property requires all left subtree nodes to be less than the current node and all right subtree nodes to be greater, strictly increasing in inorder traversal.

2. Step 2: Recognize inorder traversal pattern

   Inorder traversal of a valid BST produces a strictly increasing sequence of values, so verifying this sequence guarantees correctness efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Inorder traversal yields sorted values for BST [OK]

Hint: Inorder traversal of BST is strictly increasing [OK]

Common Mistakes:

• Only comparing node with immediate children
• Using greedy checks without global ordering
• Confusing subtree min/max with inorder sequence

3. What is the worst-case time complexity of the optimized recursive BST node deletion algorithm that uses the in-order successor to replace a node with two children?

medium

A. O(h) where h is the height of the BST

B. O(h^2) due to recursive calls and successor search

C. O(log n) always, since BST is balanced

D. O(n) where n is the total number of nodes in the BST

Solution

1. Step 1: Identify height-based operations

   Deletion involves searching down the tree (O(h)) and finding the in-order successor, which is also O(h) in worst case.

2. Step 2: Combine operations and recursion

   Successor search and recursive deletion happen along a path of length h, so total time is O(h), not O(h^2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Time proportional to tree height, not total nodes or squared height [OK]

Hint: Deletion time depends on tree height, not total nodes [OK]

Common Mistakes:

• Assuming balanced BST always (log n)
• Confusing recursion depth with squared complexity
• Thinking successor search adds extra factor

4. 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

5. The following code attempts to validate a BST using inorder traversal. Which line contains a subtle bug that can cause incorrect results on some inputs?

medium

A. Line checking if node is null (if not node: return true)

B. Line updating prev[0] = node.val

C. Line comparing node.val < prev[0] instead of node.val <= prev[0]

D. Line calling inorder(node.left)

Solution

1. Step 1: Identify BST strict inequality

   BST requires node.val to be strictly greater than previous inorder value; using < instead of <= allows duplicates.

2. Step 2: Understand impact of bug

   Using node.val < prev[0] misses the case when node.val == prev[0], incorrectly allowing duplicates and invalid BSTs.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Strict inequality check is essential to reject duplicates [OK]

Hint: BST nodes must be strictly increasing in inorder traversal [OK]

Common Mistakes:

• Allowing duplicates by using < instead of <=
• Not resetting prev between calls
• Only comparing immediate children