Insert into a Binary Search Tree - Practice Coding Problems

Insert into a Binary Search Tree - 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: 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.

Input & Output

Example 1 — Insert into Right Subtree

$ Input: root = [4,2,7,1,3], val = 5

› Output: [4,2,7,1,3,5]

💡 Note: Start at root (4): 5 > 4 so go right to 7. At node 7: 5 < 7 so go left. Left child is null, so insert 5 there.

Example 2 — Insert into Left Subtree

$ Input: root = [40,20,60,10,30,50,70], val = 25

› Output: [40,20,60,10,30,50,70,null,null,25]

💡 Note: 25 < 40 (go left) → 25 > 20 (go right) → 25 < 30 (go left). Insert 25 as left child of 30.

Example 3 — Single Node Tree

$ Input: root = [4], val = 2

› Output: [4,2]

💡 Note: Tree has only root node 4. Since 2 < 4, insert 2 as left child of root.

Constraints

The number of nodes in the tree will be in the range [0, 10⁴]
-10⁸ ≤ Node.val ≤ 10⁸
All the values Node.val are unique
-10⁸ ≤ val ≤ 10⁸
It's guaranteed that val does not exist in the original BST

Visualization

Tap to expand

Understanding the Visualization

Input BST

Given tree [4,2,7,1,3] and value 5 to insert

Navigate Tree

Follow BST property: 5>4 (right), 5<7 (left)

Insert Node

Create new node 5 as left child of 7

Key Takeaway

🎯 Key Insight: BST property guarantees exactly one valid insertion position for any new value

Asked in

a Amazon 42 M Microsoft 38 f Facebook 29 G Google 24

The key insight is to leverage the BST property: values smaller than current node go left, larger values go right. The optimal approach recursively navigates to the correct insertion point in O(h) time where h is tree height. Time: O(h), Space: O(h).

Common Approaches

Approach	Time	Space	Notes
✓ Optimal BST Insertion	O(h)	O(h)	Follow BST property to find correct insertion position
Brute Force (Rebuild Tree)	O(n log n)	O(n)	Convert tree to array, add value, rebuild balanced BST

Optimal BST Insertion — Algorithm Steps

Step 1: Start at root and compare value
Step 2: Go left if val < node.val, right if val > node.val
Step 3: Insert as new leaf when reaching null position

Visualization

Tap to expand

Step-by-Step Walkthrough

Compare with Root

5 > 4, go right

Compare with 7

5 < 7, go left

Insert New Node

Left child of 7 is null, insert 5 here

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.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* solution(struct TreeNode* root, int val) {
    if (!root) {
        return createNode(val);
    }
    
    if (val < root->val) {
        root->left = solution(root->left, val);
    } else {
        root->right = solution(root->right, val);
    }
    
    return root;
}

int main() {
    // Simplified input/output for demonstration
    struct TreeNode* root = createNode(4);
    root->left = createNode(2);
    root->right = createNode(7);
    root->left->left = createNode(1);
    root->left->right = createNode(3);
    
    int val = 5;
    struct TreeNode* result = solution(root, val);
    
    printf("[4,2,7,1,3,5]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(h)

Traverse from root to leaf, height h steps maximum

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h

✓ Linear Space

87.4K Views

Medium Frequency

~15 min Avg. Time

3.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimal BST Insertion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler