⚡Flashcard Drill➔
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

  1. A BST insert is a guided descent: go left when val is smaller, right when larger.
  2. The insertion point is the first empty slot, where a new node replaces None.
  3. The recursive form assigns the result back to the child pointer, which handles both the descent and the linking in one expression.
  4. 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 root is None: 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 val is 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems