NeetCode #422LC-701MediumTreesNC 250
← Back to All Problems#422 · #701 · Insert into a Binary Search Tree(二叉搜索树中的插入操作)
📌 Problem Statement & Constraints
You are given the root of a binary search tree and a value
val to insert. Insert the value and return the root. The input tree is guaranteed to be a valid BST and val does not already exist in it. Constraints: the number of nodes is in [0, 10^4].💡 Core Algorithmic Approaches
- A BST insert is a guided descent: go left when
valis smaller, right when larger. - The insertion point is the first empty slot, where a new node replaces
None. - The recursive form assigns the result back to the child pointer, which handles both the descent and the linking in one expression.
- An iterative version keeps a parent pointer and links the new node at the end.
💻 Benchmark Python3 Implementation
class Solution:
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root:
return TreeNode(val) # empty slot -> insert here
if val < root.val:
root.left = self.insertIntoBST(root.left, val)
else:
root.right = self.insertIntoBST(root.right, val)
return root
# Iterative variant
class Solution2:
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
node = TreeNode(val)
if not root:
return node
cur = root
while True:
if val < cur.val:
if cur.left:
cur = cur.left
else:
cur.left = node
return root
else:
if cur.right:
cur = cur.right
else:
cur.right = node
return root⚡ Complexity Deep Dive
⏱️ Time Complexity
O(h): the descent follows one path, where h is the tree height.
💾 Space Complexity
O(h) for the recursion, O(1) for the iterative version.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting to return the new node when
rootisNone: the insertion would be lost. - Not assigning the recursive result back:
self.insertIntoBST(root.left, val)without assignment does nothing to the tree. - Assuming the tree stays balanced: a sorted insertion order produces a degenerate tree of height n.
- Handling duplicates: the problem guarantees
valis absent, so no duplicate policy is needed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.