BST Insertion: Recursive Approach
What you'll learn: How to insert a new node into a Binary Search Tree using a recursive strategy that naturally finds the correct position.
The Core Idea
Inserting into a BST recursively mirrors how we search: start at the root and compare the new value. If it's smaller, recurse left; if larger, recurse right. When you hit a null spot, that's where the new node belongs. The beauty of recursion is that each call handles one "level" of the decision, and the base case naturally creates the new node.
Think of it like finding an empty parking spot by following directional signs: "Go left if your spot number is odd, right if even." You keep following signs until you reach an empty space—that's your spot.
How It Works
- Base case: If the current node is
null, create and return a new node with the value - Recursive case: Compare the new value with the current node's value
- If smaller: recurse on the left subtree
- If larger: recurse on the right subtree
- Return the current node (unchanged) to maintain tree structure
Conceptual Example
Inserting 15 into a BST with root 10:
- Compare
15vs10→ go right - Right child exists (
20) → compare15vs20→ go left - Left of
20isnull→ insert15here!
The recursion "unwinds" back up, returning each node to its parent, keeping the tree connected.
Why Recursion Fits BSTs
BST structure is inherently recursive—each subtree is itself a BST. Recursive insertion exploits this: solving "insert into this tree" becomes "insert into left/right subtree," which has the same structure.
Key Takeaway: Recursive BST insertion finds the correct null position by comparing values and recursing left or right, with the base case creating the new node exactly where it belongs.