Key Benefit: BSTs enable O(log n) insertion/removal (assuming a balanced tree) vs. O(n) for sorted arrays.

1. BST Insertion

Process

1. Insert at leaf nodes for simplicity (avoids restructuring the tree).
2. Traverse the tree similarly to search:
   • Compare the new value with the current node.
   • Move left if smaller, right if larger.
3. Base Case: When reaching null, create a new node and return it to the parent.

Example: Inserting 6 into a BST

• Tree: 4 (root) → right: null

• Steps:

  1. Start at root (4).
  2. 6 > 4 → Traverse right.
  3. Right subtree is null → Insert 6 as the right child.

• Result:

     4
      \\
       6
  
  

Code Overview

def insert(root, value):
    if not root:
        return TreeNode(value)  # Base case: create new node
    if value > root.val:
        root.right = insert(root.right, value)  # Assign to right
    elif value < root.val:
        root.left = insert(root.left, value)     # Assign to left
    return root

• Time Complexity: O(height) ≈ O(log n) for balanced trees.

2. BST Removal

Key Cases

1. Node has 0 or 1 child: Directly replace with its child (or null).
2. Node has 2 children: Replace with the minimum node in the right subtree (or maximum in the left subtree).