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. You are given a binary tree where each node has a unique integer value. You need to find whether a given value exists in the tree efficiently by leveraging the tree's ordering properties. Which approach guarantees the fastest search in the worst case?

easy

A. Use the BST property to decide whether to search left or right subtree at each node, recursively or iteratively.

B. Perform a breadth-first search (BFS) to find the value level by level.

C. Traverse the entire tree recursively checking each node until the value is found.

D. Use dynamic programming to store previously searched subtrees to avoid repeated work.

Solution

1. Step 1: Understand the problem constraints

   The tree is a BST, so left subtree nodes are less than the node, right subtree nodes are greater.

2. Step 2: Identify the optimal search approach

   Using the BST property allows skipping half of the tree at each step, leading to O(h) time complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   BST property guides search direction efficiently [OK]

Hint: BST property enables directed search, not full traversal [OK]

Common Mistakes:

• Thinking BFS or full traversal is optimal for BST search

2. The following code attempts to implement a BST Iterator using the Morris traversal technique. Identify the bug that can cause the tree structure to remain corrupted after iteration.

class BSTIterator:
    def __init__(self, root):
        self.current = root
        self.next_val = None
        self._advance()

    def _advance(self):
        while self.current:
            if not self.current.left:
                self.next_val = self.current.val
                self.current = self.current.right
                return
            else:
                pre = self.current.left
                while pre.right and pre.right != self.current:
                    pre = pre.right
                if not pre.right:
                    pre.right = self.current
                    self.current = self.current.left
                else:
                    # BUG: Missing restoration of thread
                    self.next_val = self.current.val
                    self.current = self.current.right

medium

A. Line resetting pre.right to null is missing, so threads are not removed.

B. Line setting self.next_val = self.current.val is incorrect and should be removed.

C. Line moving self.current to self.current.left should be self.current.right instead.

D. Line initializing self.current = root in __init__ is incorrect and should be null.

Solution

1. Step 1: Identify thread restoration step

   In Morris traversal, after visiting a node, the temporary thread (pre.right) must be reset to null to restore the tree.

2. Step 2: Locate missing restoration

   The code omits resetting pre.right = None in the else block, causing the tree to remain modified after iteration.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing thread removal corrupts tree structure [OK]

Hint: Always restore threads to avoid tree corruption [OK]

Common Mistakes:

• Forgetting to remove threads
• Misplacing next_val assignment
• Incorrect current pointer updates

3. What is the time complexity of the optimal iterative approach that converts a BST to a Greater Tree using reverse inorder traversal with an explicit stack?

medium

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

B. O(n · h) where n is number of nodes and h is tree height

C. O(n · log n) due to stack operations on balanced BST

D. O(h) where h is the height of the BST because each node is visited once

Solution

1. Step 1: Identify number of nodes visited

   Each node is visited exactly once during traversal.

2. Step 2: Analyze stack operations and overall traversal

   While each node is visited once, the explicit stack can hold up to h nodes, and each push/pop operation can be considered O(1). However, in the worst case (unbalanced tree), the height h can be up to n, making the complexity O(n * h).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Worst-case complexity depends on tree height [OK]

Hint: Worst-case complexity depends on tree height [OK]

Common Mistakes:

• Assuming stack operations multiply complexity by height unnecessarily
• Confusing recursion stack space with time complexity
• Thinking balanced BST implies O(n log n) time

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

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