Watch 10 video solutions for Insert into a Binary Search Tree, a medium level problem involving Tree, Binary Search Tree, Binary Tree. This walkthrough by NeetCodeIO has 26,603 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.
Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.
Example 1:
Input: root = [4,2,7,1,3], val = 5 Output: [4,2,7,1,3,5] Explanation: Another accepted tree is:
Example 2:
Input: root = [40,20,60,10,30,50,70], val = 25 Output: [40,20,60,10,30,50,70,null,null,25]
Example 3:
Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5 Output: [4,2,7,1,3,5]
Constraints:
[0, 104].-108 <= Node.val <= 108Node.val are unique.-108 <= val <= 108val does not exist in the original BST.Problem Overview: Given the root of a Binary Search Tree (BST) and a value, insert the value into the tree while maintaining BST ordering. If the tree is empty, the new value becomes the root. Otherwise, you must find the correct leaf position where the value fits.
Approach 1: Iterative BST Traversal (O(h) time, O(1) space)
This approach walks down the tree using a loop. Starting from the root, compare val with the current node's value. Move left if the value is smaller, or right if it is larger. When you reach a null child, create a new node and attach it there. The key insight is the BST property: every comparison eliminates half of the remaining subtree, so you only traverse a single root-to-leaf path of height h. Space complexity is O(1) because the traversal uses only pointers without recursion.
Approach 2: Recursive BST Insertion (O(h) time, O(h) space)
The recursive version mirrors the definition of a BST. If the current node is null, create and return a new node with the value. Otherwise, compare the value with the current node and recursively insert into the left or right subtree. Each recursive call returns the subtree root, reconnecting the structure automatically. Time complexity remains O(h), where h is the tree height. Space complexity becomes O(h) due to the recursion stack. This version is shorter and often easier to reason about during interviews.
Both approaches rely on properties of a Binary Search Tree: all values in the left subtree are smaller, and all values in the right subtree are larger. Because of this ordering, you never need to scan the entire Binary Tree. Only a single path is explored from root to insertion point.
Recommended for interviews: Interviewers usually expect the recursive or iterative BST insertion that runs in O(h) time. Implementing both shows strong understanding of tree traversal and pointer manipulation. The iterative version demonstrates control over state without recursion, while the recursive solution highlights clean problem decomposition.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative BST Traversal | O(h) | O(1) | Preferred when minimizing memory usage and avoiding recursion stack |
| Recursive BST Insertion | O(h) | O(h) | Cleaner implementation and common in interviews for explaining BST logic |