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.