Insert into a Binary Search Tree - Solution & Explanation
Problem Statement
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:
- The number of nodes in the tree will be in the range
[0, 104]. -108 <= Node.val <= 108- All the values
Node.valare unique. -108 <= val <= 108- It's guaranteed that
valdoes not exist in the original BST.
Approach Overview
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 1: Iterative Approach
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.
Complexity
Time Complexity: O(h) where h is the height of the tree. Space Complexity: O(1) since no extra space is utilized.
Approach 2: Recursive Approach
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.
Complexity
Time Complexity: O(h), where h is the height of the tree.
Space Complexity: O(h), due to the recursive stack space.
Approach 3: Recursion
If the root node is null, we directly create a new node with the value val and return it.
If the root node's value is greater than val, we recursively insert val into the left subtree and update the root of the left subtree with the returned root node.
If the root node's value is less than val, we recursively insert val into the right subtree and update the root of the right subtree with the returned root node.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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. |
| Recursion | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Insert into a Binary Search Tree - Leetcode 701 - Python • NeetCodeIO • 28,739 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Insert into a Binary Search Tree easy or hard?
Insert into a Binary Search Tree Python/Java solution
How to solve Insert into a Binary Search Tree in O(n)?
What is the best approach for Insert into a Binary Search Tree?
Is Insert into a Binary Search Tree asked at Google/Amazon/Meta?
What data structure is used in Insert into a Binary Search Tree?
What is the time complexity of Insert into a Binary Search Tree?
Ready to solve this problem?
Practice Insert into a Binary Search Tree with our built-in code editor and test cases.
Practice on FleetCode