Trim a BST

▶

Steps

setup

Initialize root and parameters

The initial BST is constructed with root value 3, and the range [1,3] is set. No pruning has started yet.

💡 Setting up the tree and range is essential before pruning begins.

Line:

root = TreeNode(3)
root.left = TreeNode(0)
root.right = TreeNode(4)
low, high = 1, 3

💡 The tree structure and range are now ready for trimming.

setup

Move root down because root.val (3) is within [1,3]

Check if root.val is outside the range. Since 3 is within [1,3], root remains at node 3.

💡 The root must be within range to start trimming subtrees.

Line:

while root and (root.val < low or root.val > high):
    if root.val < low:
        root = root.right
    elif root.val > high:
        root = root.left

💡 Root is valid; pruning will proceed on subtrees.

fill_row

Start trimming left subtree from root (node 3)

Set current pointer 'cur' to root to begin trimming the left subtree.

💡 We will iteratively check left children to remove nodes less than low.

Line:

cur = root

💡 Starting point for left subtree pruning is root.

fill_cells

Check left child of node 3 (node 0) for pruning

Node 3's left child is node 0, which has value less than low (1). We will prune node 0 by moving left pointer to node 0's right child (node 2).

💡 Nodes less than low must be removed from the left subtree.

Line:

while cur.left and cur.left.val < low:
    cur.left = cur.left.right

💡 Pruning node 0 removes invalid left subtree nodes efficiently.

fill_cells

Move cur pointer down to left child (node 2) to continue left subtree trimming

After pruning node 0, move cur to its left child node 2 to check if further pruning is needed.

💡 We must check all left descendants for nodes less than low.

Line:

cur = cur.left

💡 Traversal continues down left subtree to prune all invalid nodes.

fill_cells

Check left child of node 2 (node 1) for pruning

Node 2's left child is node 1, which is within the range [1,3], so no pruning is needed here.

💡 Nodes within range remain untouched.

Line:

while cur.left and cur.left.val < low:
    cur.left = cur.left.right

💡 Pruning stops when left child is valid.

fill_cells

Move cur pointer down to left child (node 1) to continue left subtree trimming

Move cur to node 1 to check if it has left children needing pruning.

💡 We continue down the left subtree to ensure all nodes are valid.

Line:

cur = cur.left

💡 Traversal continues to leaf nodes for pruning checks.

fill_row

Left subtree trimming complete, start trimming right subtree from root (node 3)

Set cur pointer back to root to begin trimming the right subtree.

💡 Now we will remove nodes greater than high from the right subtree.

Line:

cur = root

💡 Right subtree pruning starts fresh from root.

fill_cells

Check right child of node 3 (node 2) for pruning

Node 3's right child is node 2, which has value greater than high (3). We prune node 2 by moving right pointer to node 2's left child (node 4).

💡 Nodes greater than high must be removed from the right subtree.

Line:

while cur.right and cur.right.val > high:
    cur.right = cur.right.left

💡 Pruning node 2 removes invalid right subtree nodes efficiently.

fill_cells

Move cur pointer down to right child (node 4) to continue right subtree trimming

Move cur to its right child node 4 to check if further pruning is needed.

💡 We continue down the right subtree to ensure all nodes are valid.

Line:

cur = cur.right

💡 Traversal continues to leaf nodes for pruning checks.

reconstruct

Return the trimmed root

The root node 3 now points to a left subtree rooted at node 2 (which has left child 1) and no right subtree. This is the trimmed BST.

💡 Returning the root completes the trimming process.

Line:

return root

💡 The final tree contains only nodes within [1,3].

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

def trimBST(root, low, high):
    # STEP 2: Move root to valid range
    while root and (root.val < low or root.val > high):
        if root.val < low:
            root = root.right  # STEP 2: root moves right
        elif root.val > high:
            root = root.left   # STEP 2: root moves left
    if not root:
        return None
    # STEP 3: Trim left subtree
    cur = root  # STEP 3
    while cur:
        while cur.left and cur.left.val < low:
            cur.left = cur.left.right  # STEP 4: prune left child
        cur = cur.left  # STEP 5: move cur down left
    # STEP 8: Trim right subtree
    cur = root  # STEP 8
    while cur:
        while cur.right and cur.right.val > high:
            cur.right = cur.right.left  # STEP 9: prune right child
        cur = cur.right  # STEP 10: move cur down right
    return root  # STEP 11

if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(0)
    root.right = TreeNode(4)
    root.left.right = TreeNode(2)
    root.left.right.left = TreeNode(1)
    low, high = 1, 3
    trimmed = trimBST(root, low, high)
    def print_inorder(node):
        if not node:
            return
        print_inorder(node.left)
        print(node.val, end=' ')
        print_inorder(node.right)
    print_inorder(trimmed)

📊

Trim a BST - Watch the Algorithm Execute, Step by Step

Watching each pointer move and subtree adjustment helps you understand how BST properties enable efficient pruning without recursion.

Current node: 0

30421

Current node: 0

30421

Current node: 0

30421

DFS Stack

0 (entered)cur=0

Current node: 0

30421

DFS Stack

0 (left_done)cur=0

Current node: 3

30421

DFS Stack

0 (left_done)cur=3

Current node: 3

30421

DFS Stack

0 (left_done)cur=3

Current node: 4

30421

DFS Stack

0 (left_done)cur=4

Current node: 0

30421

DFS Stack

0 (right_entered)cur=0

Current node: 0

30421

DFS Stack

0 (right_done)cur=0

Current node: 4

30421

DFS Stack

0 (right_done)cur=4

Current node: 0

32104

Return: 0

Key Takeaways

✓ The root is first moved to a valid node within the range before any pruning.

This step ensures the trimmed tree's root is always valid, which is not obvious from code alone.

✓ Left subtree pruning removes nodes less than low by adjusting left pointers iteratively.

Seeing pointer updates visually clarifies how pruning avoids recursion and preserves BST structure.

✓ Right subtree pruning removes nodes greater than high similarly by adjusting right pointers.

The symmetry of left and right pruning is easier to grasp when watching each pointer move.

Practice

1. Consider the following code snippet for searching a value in a BST. What will be printed when searching for the value 3 in the given tree?

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

def searchBST(root, val):
    current = root
    while current:
        if current.val == val:
            return current
        elif val < current.val:
            current = current.left
        else:
            current = current.right
    return None

root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7))
result = searchBST(root, 3)
print(result.val if result else 'null')

easy

A. 2

B. 7

C. null

D. 3

Solution

1. Step 1: Trace the search path

   Start at root (4). Since 3 < 4, move to left child (2). Since 3 > 2, move to right child (3).

2. Step 2: Check node value

   Current node value is 3, which matches the search value, so return this node.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Search follows BST property correctly and finds node with value 3 [OK]

Hint: Follow BST property to move left or right [OK]

Common Mistakes:

• Returning wrong node value due to off-by-one traversal

2. What is the average time complexity per call of next() in the Morris traversal based BST Iterator, assuming the BST has n nodes?

medium

A. O(1) amortized per next() call because each edge is visited at most twice.

B. O(n) per next() call because each call may traverse the entire tree.

C. O(h) per next() call where h is the tree height due to traversing left children.

D. O(log n) per next() call assuming a balanced BST and stack usage.

Solution

1. Step 1: Understand Morris traversal edge visits

   Each edge in the BST is visited at most twice: once to create a thread and once to remove it.

2. Step 2: Calculate amortized cost per next()

   Since total work is O(n) for n nodes, and there are n calls to next(), average cost per call is O(1) amortized.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Amortized O(1) per next() matches Morris traversal properties [OK]

Hint: Morris traversal visits edges twice total [OK]

Common Mistakes:

• Assuming worst-case O(n) per call
• Confusing with stack-based O(h)
• Ignoring amortized analysis

3. The following code attempts to convert a BST to a Greater Tree using reverse inorder traversal. Identify the line that contains a subtle bug causing incorrect node values.

medium

A. Line 8: node = node.left instead of node = node.right

B. Line 6: while node: loop condition

C. Line 10: acc_sum += node.val accumulation

D. Line 12: node = node.right traversal after updating node

Solution

1. Step 1: Understand traversal order needed

   Reverse inorder traversal requires visiting right subtree first to accumulate greater values.

2. Step 2: Identify incorrect subtree traversal

   Line 8 incorrectly moves to left child first, reversing traversal order and causing wrong sums.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing node = node.left to node = node.right fixes traversal order [OK]

Hint: Reverse inorder must traverse right subtree first [OK]

Common Mistakes:

• Swapping left and right subtree traversal order
• Resetting acc_sum inside loops
• Updating node values before traversing right subtree

4. What is the worst-case time complexity of the optimized iterative DFS with BST pruning approach for computing the range sum of a BST with n nodes and height h?

medium

A. O(h) because only nodes along the height are visited

B. O(log n) because pruning skips most nodes

C. O(n) because in worst case pruning does not skip any nodes

D. O(n log n) because each node may be visited multiple times due to stack operations

Solution

1. Step 1: Identify worst-case scenario

   Worst case occurs when all nodes fall within the range or pruning is ineffective, so all n nodes are visited.

2. Step 2: Analyze time complexity

   Each node is processed once, so time complexity is O(n). Stack operations are O(1) amortized per node.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Worst case is full traversal, O(n) time [OK]

Hint: Worst case equals full traversal of all nodes [OK]

Common Mistakes:

• Assuming pruning always reduces to O(log n)
• Confusing height h with number of nodes n

5. Suppose the BST validation problem is modified so that duplicate values are allowed only on the right subtree (i.e., node values in the right subtree can be equal to the current node). Which modification to the inorder traversal check correctly validates this variant?

hard

A. Change the comparison to node.val < prev[0] to allow duplicates on the right subtree.

B. Change the comparison to node.val < prev[0] for all nodes except when node is right child, then allow node.val == prev[0].

C. Change the comparison to node.val <= prev[0] to allow duplicates anywhere.

D. Change the comparison to node.val < prev[0] only when traversing left subtree, and node.val <= prev[0] when traversing right subtree.

Solution

1. Step 1: Understand variant allowing duplicates only on right subtree

   Duplicates allowed only if they appear in right subtree, so inorder sequence can have equal values only when moving right.

2. Step 2: Modify comparison accordingly

   During inorder traversal, allow node.val == prev[0] only if current node is right child of previous node; otherwise, enforce strict inequality.

3. Step 3: Reason why other options fail

   Change the comparison to node.val < prev[0] to allow duplicates on the right subtree. allows duplicates anywhere; Change the comparison to node.val <= prev[0] to allow duplicates anywhere. allows duplicates anywhere; Change the comparison to node.val < prev[0] only when traversing left subtree, and node.val <= prev[0] when traversing right subtree. is ambiguous and not implementable in simple inorder traversal without parent info.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Allow duplicates only on right subtree requires conditional equality check [OK]

Hint: Duplicates allowed only on right subtree require conditional comparison [OK]

Common Mistakes:

• Allowing duplicates anywhere
• Ignoring subtree direction in comparison
• Using simple <= everywhere