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.
In this approach, we start from the root and traverse the tree to find an appropriate place for the new node without recursion. At each step, we decide to move left or right depending on the value of the node compared to the value we want to insert. Once we find a suitable spot, we insert the new node as a leaf and return.
This code creates a new tree node with the given value and traverses the tree starting from the root to find the correct insertion point. It uses a loop to move left or right in the tree and finally attaches the new node as a leaf.
Time Complexity: O(h) where h is the height of the tree. Space Complexity: O(1) since no extra space is utilized.
In the recursive method, we start at the root and recursively call the function for either the left or right subtree, based on comparisons, until an appropriate leaf is found for insertion. This method utilizes the call stack to keep track of previous nodes.
This recursive solution calls itself for the relevant subtree until a leaf node is found where the new node fits, maintaining BST properties at each recursive step.
Time Complexity: O(h), where h is the height of the tree.
Space Complexity: O(h), due to the recursive stack space.
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(h) where h is the height of the tree. Space Complexity: O(1) since no extra space is utilized. |
| Recursive Approach | Time Complexity: O(h), where h is the height of the tree. |
| 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 |
Insert into a Binary Search Tree - Leetcode 701 - Python • NeetCodeIO • 26,603 views views
Watch 9 more video solutions →Practice Insert into a Binary Search Tree with our built-in code editor and test cases.
Practice on FleetCode