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. Consider the following code snippet implementing the optimal approach for Two Sum IV in BST. Given the BST with nodes [5,3,6,2,4,null,7] and target k=9, what is the value of variable s during the first iteration of the while loop?

easy

A. 9

B. 5

C. 11

D. 7

Solution

1. Step 1: Perform inorder traversal

   Inorder traversal of BST yields sorted array: [2, 3, 4, 5, 6, 7]

2. Step 2: Calculate s in first iteration

   left=0 (value=2), right=5 (value=7), s = 2 + 7 = 9

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sum matches target k=9 on first iteration [OK]

Hint: Inorder array first + last sum equals target [OK]

Common Mistakes:

• Off-by-one error in indexing left or right
• Confusing node values with indices
• Miscomputing sum s

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

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. What is the time and space complexity of the optimal inorder traversal BST validation algorithm for a tree with n nodes and height h?

medium

A. Time O(n), Space O(h) due to recursion stack where h is tree height

B. Time O(n log n), Space O(n) due to storing all nodes

C. Time O(n^2), Space O(1) because no extra data structures are used

D. Time O(n), Space O(n) because all nodes are stored during traversal

Solution

1. Step 1: Identify time complexity

   The algorithm visits each node exactly once in inorder traversal, so time is O(n).

2. Step 2: Identify space complexity

   Space is O(h) due to recursion stack, where h is the height of the tree; no extra arrays store all nodes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time and stack space proportional to tree height [OK]

Hint: Inorder traversal visits each node once, stack depth = tree height [OK]

Common Mistakes:

• Confusing recursion stack space with storing all nodes
• Assuming O(n log n) due to sorting
• Ignoring recursion stack space

5. Suppose the BST can contain duplicate values, and you want to find all nodes with a given value. Which modification to the optimal iterative search algorithm correctly finds all such nodes?

hard

A. Stop at the first found node and return it, since duplicates are not allowed in BSTs.

B. Modify the search to continue searching both left and right subtrees even after finding a matching node.

C. Traverse the entire tree recursively to collect all nodes with the target value, ignoring BST property.

D. Use a queue to perform BFS and collect all nodes with the target value efficiently.

Solution

1. Step 1: Understand duplicates in BST

   Duplicates can appear on either left or right subtree depending on BST definition.

2. Step 2: Modify search to find all matches

   After finding a node with val, continue searching both subtrees to find all duplicates.

3. Step 3: Avoid full traversal

   Using BST property to prune search still possible by checking subtrees where duplicates may exist.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Continuing search after first match finds all duplicates [OK]

Hint: Duplicates require searching both subtrees after match [OK]

Common Mistakes:

• Stopping at first match or ignoring BST property completely