Insert into a Binary Search Tree solution and explanation
Google
9 more videos on this problem
Insert into a Binary Search Tree - Leetcode 701 - PythonNeetCodeIO · 9:48 · 28K views
LeetCode 701. Insert into a Binary Search Tree (Algorithm Explained)Nick White · 10:05 · 18K views
Insert into a Binary Search Tree | Leetcode 701 | Recursive Iterative | Google Amazon | BSTNaresh Gupta · 5:44 · 2K views
Insert into a Binary Search Tree🔥| Leetcode 701 | BSTAyushi Sharma · 13:35 · 1K views
LEETCODE 701 (JAVASCRIPT) | INSERT INTO A BINARY SEARCH TREEAndy Gala · 7:44 · 1K views
Insert into a Binary Search Tree | LeetCode 701 | C++Knowledge Center · 7:44 · 1K views
Insert into a Binary Search Tree | Leet code 701 | Theory explained + Python codeSai Anish Malla · 8:06 · 1K views
Insert into a Binary Search Tree | Leetcode 701 | Live coding session 🔥🔥| Basic Tree Traversal 💯Coding Decoded · 10:44 · 311 views
Leetcode Solution - 701 Insert into a Binary Search TreeJohn Leonardo · 5:54 · 167 views
701. Insert into a Binary Search Tree ( Leetcode Problem)viralSongs · 3:26 · 145 views
The problem
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.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
node = TreeNode(val)
if not root:
return node
current = root
while True:
if val < current.val:
if current.left is None:
current.left = node
break
else:
current = current.left
else:
if current.right is None:
current.right = node
break
else:
current = current.right
return rootclass TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
TreeNode node = new TreeNode(val);
if (root == null) return node;
TreeNode curr = root;
while (true) {
if (val < curr.val) {
if (curr.left == null) {
curr.left = node;
break;
} else {
curr = curr.left;
}
} else {
if (curr.right == null) {
curr.right = node;
break;
} else {
curr = curr.right;
}
}
}
return root;
}
}#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* insertIntoBST(TreeNode* root, int val) {
TreeNode* node = new TreeNode(val);
if (!root) return node;
TreeNode* curr = root;
while (curr) {
if (val < curr->val) {
if (!curr->left) {
curr->left = node;
break;
}
curr = curr->left;
} else {
if (!curr->right) {
curr->right = node;
break;
}
curr = curr->right;
}
}
return root;
}class TreeNode {
constructor(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
function insertIntoBST(root, val) {
const node = new TreeNode(val);
if (root === null) return node;
let current = root;
while (true) {
if (val < current.val) {
if (current.left === null) {
current.left = node;
break;
}
current = current.left;
} else {
if (current.right === null) {
current.right = node;
break;
}
current = current.right;
}
}
return root;
}#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* createNode(int val) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
struct TreeNode* insertIntoBST(struct TreeNode* root, int val) {
struct TreeNode* node = createNode(val);
if (root == NULL) return node;
struct TreeNode *curr = root, *parent = NULL;
while (curr != NULL) {
parent = curr;
if (val < curr->val)
curr = curr->left;
else
curr = curr->right;
}
if (val < parent->val)
parent->left = node;
else
parent->right = node;
return root;
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode InsertIntoBST(TreeNode root, int val) {
TreeNode node = new TreeNode(val);
if (root == null) return node;
TreeNode curr = root;
while (true) {
if (val < curr.val) {
if (curr.left == null) {
curr.left = node;
break;
}
curr = curr.left;
} else {
if (curr.right == null) {
curr.right = node;
break;
}
curr = curr.right;
}
}
return root;
}
}The Python solution defines a new node and uses a loop to decide whether to traverse left or right. Upon finding the correct spot, it attaches the new node ensuring the BST properties.
Time Complexity: O(h), where h is the height of the tree.
Space Complexity: O(1).
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.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
if root is None:
return TreeNode(val)
if val < root.val:
root.left = self.insertIntoBST(root.left, val)
else:
root.right = self.insertIntoBST(root.right, val)
return rootclass TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
if (val < root.val)
root.left = insertIntoBST(root.left, val);
else
root.right = insertIntoBST(root.right, val);
return root;
}
}#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (!root) return new TreeNode(val);
if (val < root->val)
root->left = insertIntoBST(root->left, val);
else
root->right = insertIntoBST(root->right, val);
return root;
}class TreeNode {
constructor(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
function insertIntoBST(root, val) {
if (root === null) return new TreeNode(val);
if (val < root.val) {
root.left = insertIntoBST(root.left, val);
} else {
root.right = insertIntoBST(root.right, val);
}
return root;
}#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* createNode(int val) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
struct TreeNode* insertIntoBST(struct TreeNode* root, int val) {
if (root == NULL) return createNode(val);
if (val < root->val)
root->left = insertIntoBST(root->left, val);
else
root->right = insertIntoBST(root->right, val);
return root;
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode InsertIntoBST(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
if (val < root.val) {
root.left = InsertIntoBST(root.left, val);
} else {
root.right = InsertIntoBST(root.right, val);
}
return root;
}
}In Python, the recursive solution explores sub-trees by comparing values at each node, inserting the new node at its correct position, and maintaining BST properties.
Time Complexity: O(h), where h is the height of the BST.
Space Complexity: O(h) due to recursion stack overhead.
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.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function insertIntoBST(root: TreeNode | null, val: number): TreeNode | null {
if (!root) {
return new TreeNode(val);
}
if (root.val > val) {
root.left = insertIntoBST(root.left, val);
} else {
root.right = insertIntoBST(root.right, val);
}
return root;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func insertIntoBST(root *TreeNode, val int) *TreeNode {
if root == nil {
return &TreeNode{Val: val}
}
if root.Val > val {
root.Left = insertIntoBST(root.Left, val)
} else {
root.Right = insertIntoBST(root.Right, val)
}
return root
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(h), where h is the height of the tree. |
| Recursive Approach | Time Complexity: O(h), where h is the height of the BST. |
| Recursion | – |
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 |
Frequently asked questions
Is Insert into a Binary Search Tree easy or hard?
The problem is rated Medium because it requires understanding BST properties and careful pointer manipulation. The logic itself is straightforward once you recognize that only a single root-to-leaf path must be explored to find the correct insertion position.
Insert into a Binary Search Tree Python/Java solution
Both Python and Java solutions follow the same logic: compare the target value with the current node and move left or right until a null child is found. The iterative version uses a loop, while the recursive version returns the modified subtree root. Both run in O(h) time.
How to solve Insert into a Binary Search Tree in O(n)?
The algorithm follows the BST property and traverses from the root to a leaf to find the insertion point. In the worst case of a completely skewed tree, the traversal may visit every node along a single path, leading to O(n) time complexity. Balanced trees reduce this to O(log n).
What is the best approach for Insert into a Binary Search Tree?
The standard approach is to traverse the BST from the root and compare the value at each step, moving left or right until a null position is found. Both iterative and recursive implementations achieve O(h) time complexity, where h is the height of the tree. The iterative approach uses O(1) extra space, while recursion uses O(h) stack space.
Is Insert into a Binary Search Tree asked at Google/Amazon/Meta?
BST insertion is a fundamental tree operation frequently used in technical interviews at companies like Amazon, Google, and Meta. While the direct problem may appear in coding rounds, it is often tested as part of larger BST design or tree traversal questions.
What data structure is used in Insert into a Binary Search Tree?
The problem uses a Binary Search Tree data structure, which is a specialized form of a binary tree where each node maintains sorted ordering: left subtree values are smaller and right subtree values are larger. This ordering allows efficient search and insertion operations.
What is the time complexity of Insert into a Binary Search Tree?
Insertion in a Binary Search Tree takes O(h) time, where h is the height of the tree. In a balanced BST, the height is O(log n), making insertion O(log n). In the worst case (a skewed tree), the height becomes O(n), resulting in O(n) insertion time.