Course contentsShow
← Computer Science
Lesson 506 of 2,87212. Binary Search TreesFree lesson

BST Insertion: Recursive Approach

Insert a new node by recursively finding the correct position while maintaining the BST property.

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

  1. Base case: If the current node is null, create and return a new node with the value
  2. 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
  3. Return the current node (unchanged) to maintain tree structure

Conceptual Example

Inserting 15 into a BST with root 10:

  • Compare 15 vs 10 → go right
  • Right child exists (20) → compare 15 vs 20 → go left
  • Left of 20 is null → insert 15 here!

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.