Domain 2MediumMEDIUM

Insert into a Binary Search Tree

LeetCode problem 701: Insert into a Binary Search Tree (medium).

Domain: medium•Updated: 2026-08-30
#Tree

Problem Breakdown

We need to maintain the Binary Search Tree (BST) property: for every node, all values in its left subtree must be smaller than itself, and all values in its right subtree must be larger. We are given a valid BST root and an integer val that is guaranteed not to exist yet. Our goal is to find the correct leaf position where this new value fits logically (left if smaller, right if larger) and attach it there.

Inputs:

  • root: The current head of the BST (TreeNode). Can be None.
  • val: An integer representing the new node’s key.

Outputs:

  • Returns the updated root of the tree after insertion (which might change if we insert into an empty tree).

Constraints & Edge Cases:

  • Empty Tree: If root is initially None, this becomes a single-node BST immediately.
  • Deep Trees: The recursion depth depends on height HH. Python’s default stack limit handles typical LC constraints (10410^4 nodes), but skewed trees could theoretically hit limits in other languages (handled by iterative approach if needed).
  • Values: Negative values are valid; comparison logic remains consistent.

Intuition

A brute force approach might involve traversing the tree to find a leaf and then inserting, which is essentially what we do anyway. However, since it’s a BST, we don’t need to search randomly; we can navigate directly using comparisons (val<node.valval < node.val or val>node.valval > node.val).

Key Insight: The insertion point in a BST always corresponds to the first None child encountered during traversal from the root following BST rules. We do not need to store parent pointers if we use recursion, because each recursive call returns the updated subtree reference back up the stack. This allows us to attach the new node directly at the correct location without modifying existing nodes’ values or structure unnecessarily.

Why Brute Force is Insufficient: A naive O(N)O(N) search that ignores BST properties (e.g., checking every node) would be inefficient (O(H×N)O(H \times N) if not careful). Using BST logic ensures we only traverse one path from root to leaf, making it proportional to the tree height.

Approach

  1. Base Case: If root is None, this means we’ve reached a valid insertion point (an empty spot in an existing subtree or the whole tree was empty). We create and return a new node with val.
  2. Recursive Step: Compare val with current node.val:
    • If val < node.val: Recursively insert into the left child (root.left = self.insertIntoBST(root.left, val)).
    • If val > node.val: Recursively insert into the right child (root.right = ...).
  3. Return: Return the current node after updating its children references to reflect any changes made in subtrees.

Complexity Analysis

  • Time Complexity: O(H)O(H), where HH is the height of the tree. In a balanced BST, this is O(log⁡N)O(\log N). In a skewed (linked-list-like) BST, it degrades to O(N)O(N). We only traverse one path down from root to leaf for insertion.
  • Space Complexity: O(H)O(H) due to recursion stack usage in the worst case. An iterative solution would reduce this to O(1)O(1) auxiliary space, but recursive is cleaner and standard for tree modifications unless memory constraints are tight.

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def insertIntoBST(root: 'TreeNode', val: int) -> 'TreeNode':
    # Base case: If current node is None, create new leaf here.
    if not root:
        return TreeNode(val)
    
    # Traverse down the BST path based on value comparison.
    if val < root.val:
        root.left = insertIntoBST(root.left, val)
    else:
        root.right = insertIntoBST(root.right, val)
        
    # Return current node as it remains the head of this subtree (possibly modified).
    return root

Edge Cases Handled

  • Empty Tree (root is None): The base case returns a new TreeNode(val) immediately.
  • Insertion at Root: If tree has one node and we insert smaller/larger value, recursion updates the left/right pointer of root correctly.
  • Deeply Skewed Trees: Logic holds regardless of height; complexity is strictly bound by path length to insertion point.