Insert into a Binary Search Tree — LC 701 Recursive and Iterative

Problem Statement#

LeetCode 701 — Insert into a Binary Search Tree | Difficulty: Medium

You are given the root node of a binary search tree and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST. Note that there may exist multiple valid ways for the insertion — just return any of them.

Constraints:

• The number of nodes is in the range [0, 10^4]
• -10^8 <= Node.val <= 10^8
• All the values are unique
• -10^8 <= val <= 10^8

Input:  root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]

Input:  root = [40,20,60,10,30,50,70], val = 25
Output: [40,20,60,10,30,50,70,null,null,25]

Why This Problem Matters#

BST insertion is a foundational operation that every software engineer needs to understand. Amazon and Microsoft ask it as a warmup or as part of larger BST design questions. While the algorithm itself is simple, the problem tests whether you understand BST invariants and can implement them cleanly in both recursive and iterative form.

The recursive approach is elegant and matches the structure of BST problems like search and deletion. The iterative approach avoids recursion overhead and is preferred in production code for large trees. Understanding both is essential for FAANG interviews.

The Core Insight#

In a BST, the insertion point is always a leaf position. The value's final location is uniquely determined by the BST invariant:

• If val < node.val: go left
• If val > node.val: go right
• If the target direction is null: insert here

No rebalancing is needed for a plain BST insertion (unlike AVL or red-black trees). The BST invariant is automatically maintained because we only insert at a null leaf position that is consistent with all ancestor comparisons.

Visual Dry Run#

Insert 5 into [4, 2, 7, 1, 3]:

Result: 5 becomes the left child of 7.

Solution (Optimal)#

class Solution:
    def insertIntoBST(self, root, val: int):
        # Base case: found the insertion point (null position)
        if not root:
            return TreeNode(val)
 
        if val < root.val:
            root.left = self.insertIntoBST(root.left, val)
        else:
            root.right = self.insertIntoBST(root.right, val)
 
        return root

var insertIntoBST = function(root, val) {
    // Null position — this is where the new node goes
    if (!root) return new TreeNode(val);
 
    if (val < root.val) {
        root.left = insertIntoBST(root.left, val);
    } else {
        root.right = insertIntoBST(root.right, val);
    }
 
    return root;
};

Iterative version (preferred for large trees):

def insertIntoBST(self, root, val: int):
    if not root:
        return TreeNode(val)
 
    node = root
    while True:
        if val < node.val:
            if not node.left:
                node.left = TreeNode(val)
                return root
            node = node.left
        else:
            if not node.right:
                node.right = TreeNode(val)
                return root
            node = node.right

Time: O(h) — h is tree height; O(log n) balanced, O(n) skewed Space: O(h) recursive (call stack), O(1) iterative

Common Mistakes#

• Returning the new node instead of root at the end of the recursive function — this would replace the entire subtree with just the new node
• Forgetting to assign back: root.left = insertIntoBST(root.left, val) — without assignment, the insertion is lost
• Trying to insert at an internal node (not at a leaf) — BST insertion always places the new node at a leaf
• Not handling the empty tree case (null root) — must return a new node when root is null

Interview Tips#

• State that BST insertion always places the new node at a leaf — this shows you understand the invariant
• Show both recursive and iterative implementations if time allows
• Mention that this is O(h) where h = tree height, and explain the difference for balanced vs skewed trees
• Connect to BST deletion (LC 450) — deletion is harder, but insertion is the foundation

Follow-up Questions#

• How does this change for an AVL tree? After insertion, check balance factors and perform rotations (LL, RR, LR, RL) to restore balance.
• What if duplicates are allowed? Decide whether duplicates go left or right, and be consistent. Standard BST practice disallows duplicates.
• How would you insert a range of values efficiently? Use bulk insertion with sorted input — insert values in level-order to create a balanced BST.
• What is the worst-case insertion sequence? Inserting already-sorted values creates a degenerate (linked-list shaped) BST with O(n) height.
• How does a self-balancing BST (AVL, Red-Black) handle this? Same path traversal, but with rebalancing rotations on the way back up.

Key Takeaways#

• BST insertion always places the new node at a leaf — no rebalancing needed for a plain BST
• Navigate left if val < node.val, right if val > node.val, insert when you reach null
• The recursive version returns the modified subtree root — always assign back: root.left = insert(root.left, val)
• The iterative version is O(1) space and preferred in production — traverse with a pointer, attach at the first null
• Time O(h): O(log n) for balanced BST, O(n) for skewed BST (sorted insertion)
• The empty tree case is critical: return a new node when root is null
• Understanding BST insertion is the foundation for deletion (LC 450), validation (LC 98), and self-balancing tree operations