Insert into a Binary Search Tree (LeetCode 701)
You're handed the root of a binary search tree (BST) plus a value that needs a home in it. Splice the value in and hand back the root of the updated BST. The value is guaranteed to be new — it isn't already in the tree.
There's often more than one legal spot for the new node; any placement that keeps the BST ordering intact is accepted.
Worked Examples
root = [4,2,7,1,3], val = 5[4,2,7,1,3,5]5 is bigger than 4 and smaller than 7, so it becomes 7's left child. Other valid BSTs that contain 5 are accepted too.root = [40,20,60,10,30,50,70], val = 25[40,20,60,10,30,50,70,null,null,25]25 goes left of 40, right of 20, then into the empty left spot under 30.root = [4,2,7,1,3,null,null,null,null,null,null], val = 5[4,2,7,1,3,5]5 is bigger than 4 and smaller than 7, so it becomes 7's left child.⚖️Formal Constraints & Bounds
The number of nodes in the tree will be in the range
[0, 104].-108 <= Node.val <= 108All the values
Node.valare unique.-108 <= val <= 108It's guaranteed that
valdoes not exist in the original BST.
Core Insight
Re-assigning child pointers root.left = insert(root.left, val) cleanly updates tree topology without parent pointers.
Real-World Scenario & Production Applications
Dynamic symbol table updates, fast key insertion in database trees.
Subproblems & Recurrence Decomposition3 Phases
Recursing past a leaf's child lands on None -- that's exactly where the new value belongs, so a fresh TreeNode(val) is returned to be spliced in by the parent frame.
if not root:
return TreeNode(val)Step-by-Step Execution Trace Table
| Current Node | Comparison vs val=5 | Action |
|---|---|---|
| 4 | 5 > 4 | Recurse right to node 7 |
| 7 | 5 < 7 | Recurse left to null |
| None | Base case | Return TreeNode(5) -> node7.left = TreeNode(5) |
root = [4,2,7,1,3], val = 5[4,2,7,1,3,5]| Current Node | Comparison vs val=5 | Action |
|---|---|---|
| 4 | 5 > 4 | Recurse right to node 7 |
| 7 | 5 < 7 | Recurse left to null |
| None | Base case | Return TreeNode(5) -> node7.left = TreeNode(5) |
| 1 | if not root: |
| 2 | return TreeNode(val) |
| 3 | if val < root.val: |
| 4 | root.left = insertIntoBST(root.left, val) |
| 5 | else: |
| 6 | root.right = insertIntoBST(root.right, val) |
| 7 | return root |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A Binary Search Tree (BST) enforces a strict spatial contract: for every node, all values in its left subtree are strictly smaller than its own value, and all values in its right subtree are strictly larger. Inserting a new value into a BST never requires rebalancing or rearranging existing nodes. Because the tree's ordering invariant is absolute, there exists a unique empty slot (a null pointer at a leaf boundary) where the new value naturally belongs. The search for this slot is completely deterministic, running in time where is the tree height.
🏟️ The Analogy: Parking in an Automated Valet Garage
Imagine driving into a tiered valet garage where cars are sorted by size. At the entrance gate, a scanner checks your car length. If your car is smaller than the gate's reference car, an automated sign directs you: "Turn Left". At the next intersection, your car is compared again. If it is larger, the sign directs: "Turn Right". You continue following the binary directional signs at each junction until you reach an empty designated parking stall at the end of the aisle. You park in that vacant spot without moving any other vehicle.
🔑 Why It Works
The recursive pattern root.left = insert(root.left, val) is the "pointer reconnection idiom". At the leaf boundary, the base case creates and returns the new node. The parent node reassigns its null pointer to this new child, while all ancestor nodes simply reconnect their existing subtrees unharmed as recursion unwinds.
Severing child links on recursion: Writing
root.left = insertIntoBST(root.left, val)is clean, but forgetting to returnrootat the end returnsNoneto parent callers.Inserting duplicates into BST: If
val == root.val, standard BST insertion must specify behavior (usually inserting right or disallowing duplicates).Base case allocation: The base case
if not root: return TreeNode(val)must create the new leaf node and return it to be attached.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
BST dynamic insertion while maintaining sorted tree topology.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: re-linking root.left = insert(root.left, val) preserves the BST invariant along the search path.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Modifying root reference instead of re-linking child pointers.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I compare val against root.val. If val < root.val, I recursively insert into left subtree and re-link root.left; otherwise into right subtree. When root is None, I return TreeNode(val). Runs in O(H) time and O(H) call-stack space."
Complexity & Mathematical Proof
O(H)
Look at the execution steps: Traverses single path from root to leaf by comparing val with node.val in O(1) time. Inserts new TreeNode at leaf. Path length equals tree height H.
O(H) Auxiliary
Call stack depth equals tree height H (or O(1) space if implemented iteratively).
T(H) = H comparisons = O(H)
Derivation Progression
if val < node.val: go left else go right
Follows unique path down the BST in O(1) comparison per level.
node.left/right = TreeNode(val)
Attaches new node at leaf position in O(1) pointer assignment.
H ≤ N ⟹ O(H)
Runs in time proportional to tree height.
Variable Definitions
Total number of nodes in the BST
Tree height (log N in balanced tree, N in skewed tree)
Memory Architecture & Bounds
O(H) Recursive stack frames (O(1) if iterative)
O(1) One new TreeNode allocation
O(1) Root reference
Boundary Best / Worst Cases
if inserting into empty root, on balanced BST.
.
on degenerate skewed tree.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "insert into a binary search tree". Functional recursive tree splicing: the function returns the root of the modified subtree.
, values distinct. Time budget where .
Insert into a Binary Search Tree (LeetCode 701)
You're handed the root of a binary search tree (BST) plus a value that needs a home in it. Splice the value in and hand back the root of the updated BST. The value is guaranteed to be new — it isn't already in the tree.
There's often more than one legal spot for the new node; any placement that keeps the BST ordering intact is accepted.
Worked Examples
root = [4,2,7,1,3], val = 5[4,2,7,1,3,5]5 is bigger than 4 and smaller than 7, so it becomes 7's left child. Other valid BSTs that contain 5 are accepted too.root = [40,20,60,10,30,50,70], val = 25[40,20,60,10,30,50,70,null,null,25]25 goes left of 40, right of 20, then into the empty left spot under 30.root = [4,2,7,1,3,null,null,null,null,null,null], val = 5[4,2,7,1,3,5]5 is bigger than 4 and smaller than 7, so it becomes 7's left child.⚖️Formal Constraints & Bounds
The number of nodes in the tree will be in the range
[0, 104].-108 <= Node.val <= 108All the values
Node.valare unique.-108 <= val <= 108It's guaranteed that
valdoes not exist in the original BST.
Core Insight
Re-assigning child pointers root.left = insert(root.left, val) cleanly updates tree topology without parent pointers.
Real-World Scenario & Production Applications
Dynamic symbol table updates, fast key insertion in database trees.
Subproblems & Recurrence Decomposition3 Phases
Recursing past a leaf's child lands on None -- that's exactly where the new value belongs, so a fresh TreeNode(val) is returned to be spliced in by the parent frame.
if not root:
return TreeNode(val)Step-by-Step Execution Trace Table
| Current Node | Comparison vs val=5 | Action |
|---|---|---|
| 4 | 5 > 4 | Recurse right to node 7 |
| 7 | 5 < 7 | Recurse left to null |
| None | Base case | Return TreeNode(5) -> node7.left = TreeNode(5) |
root = [4,2,7,1,3], val = 5[4,2,7,1,3,5]| Current Node | Comparison vs val=5 | Action |
|---|---|---|
| 4 | 5 > 4 | Recurse right to node 7 |
| 7 | 5 < 7 | Recurse left to null |
| None | Base case | Return TreeNode(5) -> node7.left = TreeNode(5) |
| 1 | if not root: |
| 2 | return TreeNode(val) |
| 3 | if val < root.val: |
| 4 | root.left = insertIntoBST(root.left, val) |
| 5 | else: |
| 6 | root.right = insertIntoBST(root.right, val) |
| 7 | return root |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A Binary Search Tree (BST) enforces a strict spatial contract: for every node, all values in its left subtree are strictly smaller than its own value, and all values in its right subtree are strictly larger. Inserting a new value into a BST never requires rebalancing or rearranging existing nodes. Because the tree's ordering invariant is absolute, there exists a unique empty slot (a null pointer at a leaf boundary) where the new value naturally belongs. The search for this slot is completely deterministic, running in time where is the tree height.
🏟️ The Analogy: Parking in an Automated Valet Garage
Imagine driving into a tiered valet garage where cars are sorted by size. At the entrance gate, a scanner checks your car length. If your car is smaller than the gate's reference car, an automated sign directs you: "Turn Left". At the next intersection, your car is compared again. If it is larger, the sign directs: "Turn Right". You continue following the binary directional signs at each junction until you reach an empty designated parking stall at the end of the aisle. You park in that vacant spot without moving any other vehicle.
🔑 Why It Works
The recursive pattern root.left = insert(root.left, val) is the "pointer reconnection idiom". At the leaf boundary, the base case creates and returns the new node. The parent node reassigns its null pointer to this new child, while all ancestor nodes simply reconnect their existing subtrees unharmed as recursion unwinds.
Severing child links on recursion: Writing
root.left = insertIntoBST(root.left, val)is clean, but forgetting to returnrootat the end returnsNoneto parent callers.Inserting duplicates into BST: If
val == root.val, standard BST insertion must specify behavior (usually inserting right or disallowing duplicates).Base case allocation: The base case
if not root: return TreeNode(val)must create the new leaf node and return it to be attached.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
BST dynamic insertion while maintaining sorted tree topology.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: re-linking root.left = insert(root.left, val) preserves the BST invariant along the search path.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Modifying root reference instead of re-linking child pointers.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I compare val against root.val. If val < root.val, I recursively insert into left subtree and re-link root.left; otherwise into right subtree. When root is None, I return TreeNode(val). Runs in O(H) time and O(H) call-stack space."
Complexity & Mathematical Proof
O(H)
Look at the execution steps: Traverses single path from root to leaf by comparing val with node.val in O(1) time. Inserts new TreeNode at leaf. Path length equals tree height H.
O(H) Auxiliary
Call stack depth equals tree height H (or O(1) space if implemented iteratively).
T(H) = H comparisons = O(H)
Derivation Progression
if val < node.val: go left else go right
Follows unique path down the BST in O(1) comparison per level.
node.left/right = TreeNode(val)
Attaches new node at leaf position in O(1) pointer assignment.
H ≤ N ⟹ O(H)
Runs in time proportional to tree height.
Variable Definitions
Total number of nodes in the BST
Tree height (log N in balanced tree, N in skewed tree)
Memory Architecture & Bounds
O(H) Recursive stack frames (O(1) if iterative)
O(1) One new TreeNode allocation
O(1) Root reference
Boundary Best / Worst Cases
if inserting into empty root, on balanced BST.
.
on degenerate skewed tree.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "insert into a binary search tree". Functional recursive tree splicing: the function returns the root of the modified subtree.
, values distinct. Time budget where .