Insert into a BST

▶

Steps

setup

Check if tree is empty

The algorithm checks if the root is None. Since the root exists, it proceeds to initialize pointers.

💡 This step handles the edge case of an empty tree by creating a new root if needed.

Line:

if root is None:
    return TreeNode(val)

💡 We know the tree is non-empty, so insertion will be done by traversing existing nodes.

setup

Initialize pointers: curr = root, parent = None

Set current pointer to root node (4) and parent pointer to None before traversal begins.

💡 These pointers help track the current node being inspected and its parent for insertion.

Line:

curr = root
parent = None

💡 We start traversal at the root with no parent yet.

compare

Compare val with curr.val (5 > 4)

Compare the value to insert (5) with current node's value (4). Since 5 > 4, decide to move to the right child.

💡 This comparison decides the traversal direction to maintain BST order.

Line:

if val < curr.val:
    ...
else:
    curr = curr.right

💡 Values greater than current node go to the right subtree.

traverse

Update parent to 4 and move curr to right child (7)

Before moving current pointer to right child (7), update parent pointer to current node (4).

💡 Parent pointer tracks the node above current to attach new node later.

Line:

parent = curr
curr = curr.right

💡 Parent always trails current to know where to insert.

compare

Compare val with curr.val (5 < 7)

Compare value to insert (5) with current node's value (7). Since 5 < 7, decide to move to the left child.

💡 This comparison guides traversal to the left subtree to maintain BST order.

Line:

if val < curr.val:
    curr = curr.left

💡 Values smaller than current node go to the left subtree.

traverse

Update parent to 7 and move curr to left child (null)

Update parent pointer to current node (7) before moving current pointer to its left child, which is null indicating insertion point.

💡 Parent pointer tracks the node above current to attach new node later.

Line:

parent = curr
curr = curr.left

💡 Parent always trails current to know where to insert.

insert

Insert new node as left child of 7

Since current node (7) has no left child, insert new node with value 5 as left child.

💡 Finding a null child pointer is where insertion happens to maintain BST structure.

Line:

if curr.left is None:
    curr.left = TreeNode(val)
    return root

💡 Insertion point found; new node attached as left child.

insert

Return updated root after insertion

Insertion complete, return the original root node which now includes the new node.

💡 Returning root allows the updated tree to be used by the caller.

Line:

return root

💡 The tree structure is updated and ready for further operations or output.

reconstruct

Perform inorder traversal to verify BST

Perform inorder traversal to produce sorted list of node values, verifying BST property after insertion.

💡 Inorder traversal of BST yields sorted values, confirming correct insertion.

Line:

def inorder(node):
    return inorder(node.left) + [node.val] + inorder(node.right) if node else []
print(inorder(root))

💡 The output list shows the tree nodes in ascending order including the new value.

reconstruct

Final BST with inserted value

The final BST includes the new node with value 5 as left child of 7, maintaining BST properties.

💡 This final state confirms the insertion is complete and correct.

💡 The tree structure and inorder traversal confirm the algorithm's correctness.

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

def insertIntoBST(root, val):
    # STEP 1: Check if tree is empty
    if root is None:
        return TreeNode(val)  # STEP 1
    curr = root  # STEP 2
    parent = None  # STEP 2
    while curr:  # STEP 3
        parent = curr  # STEP 4
        if val < curr.val:  # STEP 3
            if curr.left is None:  # STEP 6
                curr.left = TreeNode(val)  # STEP 7
                return root  # STEP 8
            curr = curr.left  # STEP 5
        else:
            if curr.right is None:  # Not reached in this example
                curr.right = TreeNode(val)
                return root
            curr = curr.right  # STEP 3
    return root

# Driver code
if __name__ == '__main__':
    root = TreeNode(4)
    root.left = TreeNode(2, TreeNode(1), TreeNode(3))
    root.right = TreeNode(7)
    val = 5
    root = insertIntoBST(root, val)
    def inorder(node):
        return inorder(node.left) + [node.val] + inorder(node.right) if node else []
    print(inorder(root))  # STEP 9

📊

Insert into a BST - Watch the Algorithm Execute, Step by Step

Watching each pointer move and comparison helps you understand how BST insertion preserves order and structure.

42713

Current node: 1

42713

Current node: 1

42713

Current node: 3

42713

42713

42713

Current node: 6

427135

427135

Return: 1

427135

Result: [1, 2, 3, 4, 5, 7]

427135

Result: [1, 2, 3, 4, 5, 7]

Return: 1

Key Takeaways

✓ Insertion in BST is done by traversing from root to the correct leaf position based on comparisons.

This traversal logic is hard to visualize from code alone but becomes clear when watching pointer moves.

✓ Parent pointer is essential to attach the new node once the correct null child is found.

Understanding the role of parent helps clarify how the tree structure is modified.

✓ Inorder traversal after insertion confirms the BST property is maintained and the new value is correctly placed.

Seeing the sorted output visually confirms correctness beyond just code inspection.

Practice

1. You are given a binary search tree (BST) that has become skewed after multiple insertions and deletions, causing inefficient search operations. Which approach best guarantees transforming this BST into a balanced BST with minimal height to optimize search times?

easy

A. Perform a preorder traversal and rebuild the BST using the traversal order.

B. Use a greedy approach to rotate nodes locally to balance the tree without full traversal.

C. Apply dynamic programming to find the optimal subtree splits for balancing.

D. Perform an inorder traversal to collect nodes in sorted order, then rebuild the BST by recursively choosing the middle node as root.

Solution

1. Step 1: Understand traversal order for BST

   Inorder traversal of a BST produces nodes in sorted order, which is essential for rebuilding a balanced BST.

2. Step 2: Rebuild balanced BST from sorted nodes

   Choosing the middle node as root recursively ensures minimal height and balanced structure.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Inorder traversal + middle node rebuild -> balanced BST [OK]

Hint: Inorder traversal yields sorted nodes for balanced rebuild [OK]

Common Mistakes:

• Using preorder or postorder traversal which do not guarantee sorted order
• Trying local rotations greedily without global structure knowledge
• Misapplying DP where recursion on sorted nodes suffices

2. Given the following code for finding the kth smallest element in a BST, what is the returned value when called with k=2 on the provided tree?

from typing import Optional

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

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

# Tree:
#     3
#    / \
#   1   4
#    \
#     2

root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
print(kthSmallest(root, 2))

easy

A. 3

B. 1

C. 2

D. 4

Solution

1. Step 1: Trace the inorder traversal steps

   Stack initially empty, current=root(3). Push 3, move left to 1. Push 1, move left to None. Pop 1 (count=1), move right to 2.

2. Step 2: Continue traversal to find kth=2

   Push 2, move left None. Pop 2 (count=2), return 2 as kth smallest.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Second smallest in BST is 2 [OK]

Hint: Inorder traversal visits nodes in ascending order [OK]

Common Mistakes:

• Off-by-one counting of k
• Returning before incrementing count

3. Consider the following code for computing the range sum of a BST. Given the BST with root value 10, left child 5, right child 15, and range [7, 15], what is the final value of total returned by rangeSumBST?

easy

A. 25

B. 15

C. 40

D. 30

Solution

1. Step 1: Trace initial stack and total

   Start with stack=[10], total=0.

2. Step 2: Pop 10 (in range), add 10, push left(5) and right(15)

   total=10, stack=[5,15]

3. Step 3: Pop 15 (in range), add 15, push left(null) and right(null)

   total=25, stack=[5,null,null]

4. Step 4: Pop null (skip), then pop null (skip), then pop 5 (less than low=7), push right(null)

   total=25, stack=[null]

5. Step 5: Pop null (skip), stack empty, return total=25

   5 is less than low, so it is skipped and not added.

6. Final Answer:

   Option A -> Option A

7. Quick Check:

   Sum includes 10 and 15 only, total=25 [OK]

Hint: Only nodes within [7,15] add to total [OK]

Common Mistakes:

• Adding nodes outside range
• Forgetting to push children after adding node

4. Suppose the BST can contain duplicate values and you want to find the kth smallest element counting duplicates as separate elements. Which modification to the iterative inorder traversal approach correctly handles duplicates without extra space or preprocessing?

hard

A. Perform a full inorder traversal collecting all values, then remove duplicates before indexing kth element.

B. Modify the traversal to skip nodes with duplicate values to avoid counting duplicates multiple times.

C. Use a hash set to track visited values and only increment count for unique values.

D. Keep the traversal unchanged; duplicates are naturally counted separately in inorder traversal order.

Solution

1. Step 1: Understand duplicates in BST inorder traversal

   Inorder traversal visits nodes in sorted order including duplicates as separate nodes.

2. Step 2: Check if modification is needed

   Since duplicates appear as separate nodes, counting each node visited naturally counts duplicates separately without extra logic.

3. Step 3: Evaluate other options

   Skipping duplicates (B) or using a hash set (C) changes semantics. Removing duplicates after full traversal (D) is inefficient and breaks counting duplicates separately.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Inorder traversal inherently counts duplicates separately [OK]

Hint: Duplicates appear as separate nodes in inorder traversal [OK]

Common Mistakes:

• Trying to skip duplicates
• Using extra space unnecessarily
• Assuming duplicates must be merged

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