LeetCode · #701

Insert into a Binary Search Tree Solution

Follow the BST search path until you reach a null spot, then attach the new value there as a leaf.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #701

🏗️

Pattern

BST insert — follow search path

Insert a new value into the BST and return the root of the updated tree. The inserted value is guaranteed not to already exist in the BST.

Example

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

Section Two · Approach 1

Rebuild from Inorder — Overkill

You could extract all values, insert into a sorted list, and rebuild a BST.

Problem: This throws away the whole benefit of BST insertion. The BST already tells you exactly where the new node belongs in O(h).

Section Three · Approach 2

Recursive Insert — O(h)

Compare val with the current node and recurse left or right until you hit null. That null position is where the new node should be created.

💡 Mental model: Search for where the value would be if it were already in the tree. When the search falls off the tree at a null child, that is the insertion point.

Why the return-node pattern works

The recursive call returns the updated subtree root.
The parent stores it back into node.left or node.right.
This naturally rewires the new leaf into the correct position.

Key idea: Insertion never restructures existing nodes in a plain BST. It only attaches one new leaf.

Section Four · Trace

Visual Walkthrough

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

Section Five · Implementation

Code — Java & Python

Java — recursive insert

 class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
if (val < root.val) {
            root.left = insertIntoBST(root.left, val);
        } else {
            root.right = insertIntoBST(root.right, val);
        }
return root;
    }
}

Python — recursive insert

 class Solution:
def insertIntoBST(self, root, val: int):
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

Section Six · Analysis

Complexity Analysis

Approach	Time	Space
Rebuild tree	O(n)	O(n)
BST insert	O(h)	O(h)

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Why it matters
Empty tree	The new node becomes the root.
Insert smallest value	Walk all the way down the left spine.
Insert largest value	Walk all the way down the right spine.

⚠ Common Mistake: Forgetting to reassign root.left or root.right from the recursive result. Without that, the new node never gets linked back into the tree.

← Back to BST problems

LearningTree

LC 701 · Insert into a Binary Search Tree — Solution & Explanation | DSA Guide