Log inSign up
mediumLeetCodeNot Started

Insert into a Binary Search Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on LeetCode
Lesson

Problem Statement

You are given the root node of a Binary Search Tree (BST) and a val 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.

Constraints:

  • The number of nodes in the tree will be in the range [0, 104].
  • -108 <= Node.val <= 108
  • All the values Node.val are unique.
  • -108 <= val <= 108
  • It's guaranteed that val does not exist in the original BST.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why any valid key can be inserted as a new leaf in a BST.
  • Implement the standard recursive insertion idiom with return linking.
  • Eliminate recursion overhead using iterative pointer descent.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Insert new value into BST.
  • Preserve BST ordering.
  • Output valid BST root.

Algorithmic Decision Tree:

  • If val < curr.val: recurse left curr.left = insert(curr.left, val).
  • If val > curr.val: recurse right curr.right = insert(curr.right, val).
  • If curr == null: return new TreeNode(val).

Connected Patterns:

Search in a Binary Search TreeDelete Node in a BSTConstruct BST from Preorder Traversal

1. Flatten, Insert into Sorted Array, Reconstruct Tree

Intuition

Traverse tree inorder to get array vals. Insert val into vals using binary search or insertion. Then rebuild a height-balanced BST using midpoint recursion. While correct, this takes O(N) time and O(N) auxiliary space, whereas standard BST insertion requires only O(H) time.

When to apply: When guaranteed rebalancing is required and O(N) allocation is acceptable.

Algorithm

  1. Extract all nodes via inorder traversal into an array, insert the new value into its sorted position, and rebuild a balanced BST.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4struct TreeNode {
5 int val;
6 TreeNode* left;
7 TreeNode* right;
8 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9};
10
11class Solution {
12 void inorder(TreeNode* root, std::vector<int>& vals) {
13 if (!root) return;
14 inorder(root->left, vals);
15 vals.push_back(root->val);
16 inorder(root->right, vals);
17 }
18
19 TreeNode* build(const std::vector<int>& vals, int l, int r) {
20 if (l > r) return nullptr;
21 int mid = l + (r - l) / 2;
22 TreeNode* node = new TreeNode(vals[mid]);
23 node->left = build(vals, l, mid - 1);
24 node->right = build(vals, mid + 1, r);
25 return node;
26 }
27public:
28 TreeNode* insertIntoBST(TreeNode* root, int val) {
29 std::vector<int> vals;
30 inorder(root, vals);
31
32 // Insert val in sorted order
33 std::vector<int> combined;
34 bool inserted = false;
35 for (int v : vals) {
36 if (!inserted && val < v) {
37 combined.push_back(val);
38 inserted = true;
39 }
40 combined.push_back(v);
41 }
42 if (!inserted) combined.push_back(val);
43
44 return build(combined, 0, (int)combined.size() - 1);
45 }
46};
47
48int main() {
49 TreeNode* root = new TreeNode(4);
50 root->left = new TreeNode(2);
51 root->right = new TreeNode(7);
52 root->left->left = new TreeNode(1);
53 root->left->right = new TreeNode(3);
54
55 Solution sol;
56 TreeNode* res = sol.insertIntoBST(root, 5);
57 std::cout << "Root: " << res->val << " (Right: " << res->right->val << ")" << std::endl;
58 return 0;
59}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(N)

2. Standard Recursive BST Insertion

Intuition

1. Base case: if (!root) return new TreeNode(val). 2. If val < root.val, root.left = insertIntoBST(root.left, val). 3. If val > root.val, root.right = insertIntoBST(root.right, val). 4. Return root.

When to apply: Clean, idiomatic solution for technical interviews.

Algorithm

  1. Recurse down the tree; return new TreeNode when null, and link parent left/right pointers naturally.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct TreeNode {
4 int val;
5 TreeNode* left;
6 TreeNode* right;
7 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11public:
12 TreeNode* insertIntoBST(TreeNode* root, int val) {
13 if (!root) return new TreeNode(val);
14
15 if (val < root->val) {
16 root->left = insertIntoBST(root->left, val);
17 } else {
18 root->right = insertIntoBST(root->right, val);
19 }
20
21 return root;
22 }
23};
24
25int main() {
26 TreeNode* root = new TreeNode(4);
27 root->left = new TreeNode(2);
28 root->right = new TreeNode(7);
29 root->left->left = new TreeNode(1);
30 root->left->right = new TreeNode(3);
31
32 Solution sol;
33 TreeNode* res = sol.insertIntoBST(root, 5);
34 std::cout << "Root: " << res->val << " (7.left: " << res->right->left->val << ")" << std::endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(H) where H is tree height
  • Space complexity: O(H) recursion stack space

3. Iterative Pointer Traversal (O(1) Auxiliary Space)

Intuition

1. If !root, return new TreeNode(val) immediately. 2. Set curr = root. 3. Loop indefinitely: - If val < curr.val: if curr.left == null, set curr.left = new TreeNode(val) and break; else curr = curr.left. - If val > curr.val: if curr.right == null, set curr.right = new TreeNode(val) and break; else curr = curr.right. 4. Return original root.

When to apply: Optimal in both time and auxiliary space. Ideal for high-scale systems where stack overflows must be completely prevented.

Algorithm

  1. Descend iteratively using a while-loop. When a child pointer in the desired direction is null, attach new TreeNode directly and break.

Iterative BST Insertion Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Compare with root
Visual state
Values and pointers at this exact step
tree
This tree trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Check / comparison
curr = 4: 5 > 4 -> curr has right child 7. Move curr = 7.
Decision / next transition
1
Why this step matters

Compare with root. Value 5 belongs in the right subtree.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct TreeNode {
4 int val;
5 TreeNode* left;
6 TreeNode* right;
7 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11public:
12 TreeNode* insertIntoBST(TreeNode* root, int val) {
13 if (!root) return new TreeNode(val);
14
15 TreeNode* curr = root;
16 while (true) {
17 if (val < curr->val) {
18 if (!curr->left) {
19 curr->left = new TreeNode(val);
20 break;
21 }
22 curr = curr->left;
23 } else {
24 if (!curr->right) {
25 curr->right = new TreeNode(val);
26 break;
27 }
28 curr = curr->right;
29 }
30 }
31
32 return root;
33 }
34};
35
36int main() {
37 TreeNode* root = new TreeNode(4);
38 root->left = new TreeNode(2);
39 root->right = new TreeNode(7);
40 root->left->left = new TreeNode(1);
41 root->left->right = new TreeNode(3);
42
43 Solution sol;
44 TreeNode* res = sol.insertIntoBST(root, 5);
45 std::cout << "Root: " << res->val << " (7.left: " << res->right->left->val << ")" << std::endl;
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(H) where H is tree height
  • Space complexity: O(1) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Flatten, Insert into Sorted Array, Reconstruct TreeO(N)O(N)Extract all nodes via inorder traversal into an array, insert the new value into its sorted position, and rebuild a balanced BST.O(N)
2.Standard Recursive BST InsertionO(H) where H is tree heightO(H) recursion stack spaceRecurse down the tree; return new TreeNode when null, and link parent left/right pointers naturally.O(H) where H is tree height
3.Iterative Pointer Traversal (O(1) Auxiliary Space)OptimalO(H) where H is tree heightO(1) auxiliary spaceDescend iteratively using a while-loop. When a child pointer in the desired direction is null, attach new TreeNode directly and break.O(H) where H is tree height

Common Pitfalls & Crucial Edge Cases

Not returning the new node when root is null

Returning root when root == null returns null instead of the newly created node.

Missing assignment in recursion

Calling insertIntoBST(root.left, val) without assigning root.left = ... fails to attach the node.

Modifying existing node values

Overwriting node values rather than attaching a new node.

Crucial Edge Cases to Validate:

  • Empty tree (`root == null`) — Returns new TreeNode(val).
  • Inserting value smaller than all existing nodes — Becomes the leftmost leaf node.
  • Inserting value larger than all existing nodes — Becomes the rightmost leaf node.
  • Skewed tree with height 10^4 — Iterative solution runs smoothly without stack overflow.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State both approaches: recursive (concise, 5 lines) and iterative (O(1) memory, production-grade).
  2. Mention that insertion never requires rearranging existing nodes unless self-balancing (AVL/Red-Black) is requested.
  3. Handle the root == null edge case cleanly as the first line of code.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Can any valid new key always be inserted into a BST as a leaf node without modifying existing node links?

2.What is the space complexity of the iterative insertion approach?

3.What is the worst-case time complexity of inserting into a skewed BST of N nodes?

Back to DSA Sheet