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 beNone.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
rootis initiallyNone, this becomes a single-node BST immediately. - Deep Trees: The recursion depth depends on height . Python’s default stack limit handles typical LC constraints ( 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 ( or ).
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 search that ignores BST properties (e.g., checking every node) would be inefficient ( if not careful). Using BST logic ensures we only traverse one path from root to leaf, making it proportional to the tree height.
Approach
- Base Case: If
rootisNone, 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 withval. - Recursive Step: Compare
valwith currentnode.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 = ...).
- If
- Return: Return the current
nodeafter updating its children references to reflect any changes made in subtrees.
Complexity Analysis
- Time Complexity: , where is the height of the tree. In a balanced BST, this is . In a skewed (linked-list-like) BST, it degrades to . We only traverse one path down from root to leaf for insertion.
- Space Complexity: due to recursion stack usage in the worst case. An iterative solution would reduce this to 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 (
rootisNone): The base case returns a newTreeNode(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.