Insert into a Binary Search Tree

Medium
1929.

Insert into a Binary Search Tree

Insert into a Binary Search Tree is a medium coding problem on binary search and trees, asked in Amazon, Google and Microsoft interviews.

You are given the root of a binary search tree and an integer value that is not yet in the tree. Insert value and return the root of the tree.

More than one valid search tree can result, so insert it this way: search for value from the root as usual (left when it is smaller than a node, right when it is larger), and place a new node holding value at the empty spot where the search falls off the tree. Nothing else moves.

Example 1

Input
root = [4,2,7,1,3], value = 5
Output
[4,2,7,1,3,5]
Explanation
5 > 4 goes right to 7, then 5 < 7 goes left — an empty spot, so 5 becomes 7's left child.

Example 2

Input
root = [40,20,60,10,30,50,70], value = 25
Output
[40,20,60,10,30,50,70,null,null,25]
Explanation
The search goes 40 → 20 → 30 and falls off to the left of 30.

Example 3

Input
root = [], value = 5
Output
[5]
Explanation
Inserting into an empty tree makes the new node the root.

Constraints

  • The number of nodes in the tree is in the range [0, 10^4]
  • -10^8 <= Node.val <= 10^8
  • All the values Node.val are unique
  • -10^8 <= value <= 10^8
  • value does not exist in the original BST
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} value
 * @return {TreeNode}
 */
var insertIntoBST = function(root, value) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Insert into a Binary Search Tree — Problem & Solution

Insert into a Binary Search Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Insert into a Binary Search Tree is a medium coding problem on binary search and trees, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Binary Search, Trees
  • Asked at: Amazon, Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given the root of a binary search tree and an integer value that is not yet in the tree. Insert value and return the root of the tree.

More than one valid search tree can result, so insert it this way: search for value from the root as usual (left when it is smaller than a node, right when it is larger), and place a new node holding value at the empty spot where the search falls off the tree. Nothing else moves.

Example 1

Input: root = [4,2,7,1,3], value = 5
Output: [4,2,7,1,3,5]
Explanation: 5 > 4 goes right to 7, then 5 < 7 goes left — an empty spot, so 5 becomes 7's left child.

Example 2

Input: root = [40,20,60,10,30,50,70], value = 25
Output: [40,20,60,10,30,50,70,null,null,25]
Explanation: The search goes 40 → 20 → 30 and falls off to the left of 30.

Example 3

Input: root = [], value = 5
Output: [5]
Explanation: Inserting into an empty tree makes the new node the root.

Constraints

  • The number of nodes in the tree is in the range [0, 10^4]
  • -10^8 <= Node.val <= 10^8
  • All the values Node.val are unique
  • -10^8 <= value <= 10^8
  • value does not exist in the original BST

Hints for Insert into a Binary Search Tree

  1. Hint 1

    Where would a search for value end? At a node whose child on the side value points to is missing.

  2. Hint 2

    That missing child is exactly where the new node goes; the tree stays a valid search tree.

  3. Hint 3

    Walk down iteratively and keep the current node, or recurse and return the subtree's root so the parent can reattach it. Don't forget the empty tree.

How to solve Insert into a Binary Search Tree

A search for a missing value ends at an empty child pointer, and that position is consistent with every ancestor's ordering. Hanging the new node there is the simplest valid insertion and leaves the rest of the tree untouched.

Approach

  1. If root is null, return a new node holding value.
  2. Start at cur = root. If value < cur.val, look at cur.left; otherwise at cur.right.
  3. If that child is null, attach the new node there and stop; otherwise move to it and repeat.
  4. Return root.

Why it works

At each step value goes to the side the search-tree property requires relative to the current node, so on the final path every ancestor sees it on its correct side. Attaching a leaf changes no other link, so all other order relations still hold.

Complexity

  • Time — O(h), the tree's height — O(log n) when balanced, O(n) for a chain
  • Space — O(1) iteratively (O(h) recursively)

Pitfalls

  • The empty tree: the new node is the root.
  • Do not try to rebalance or insert higher up — the statement fixes the insertion as a new leaf.

Reference solution

Python

from typing import Optional

def insertIntoBST(root: Optional[TreeNode], value: int) -> Optional[TreeNode]:
    node = TreeNode(value)
    if root is None:
        return node
    cur = root
    while True:
        if value < cur.val:
            if cur.left is None:
                cur.left = node
                break
            cur = cur.left
        else:
            if cur.right is None:
                cur.right = node
                break
            cur = cur.right
    return root

Java

public static TreeNode insertIntoBST(TreeNode root, int value) {
    TreeNode node = new TreeNode(value);
    if (root == null) return node;
    TreeNode cur = root;
    while (true) {
        if (value < cur.val) {
            if (cur.left == null) { cur.left = node; break; }
            cur = cur.left;
        } else {
            if (cur.right == null) { cur.right = node; break; }
            cur = cur.right;
        }
    }
    return root;
}

C++

TreeNode* insertIntoBST(TreeNode* root, int value) {
    TreeNode* node = new TreeNode(value);
    if (!root) return node;
    TreeNode* cur = root;
    while (true) {
        if (value < cur->val) {
            if (!cur->left) { cur->left = node; break; }
            cur = cur->left;
        } else {
            if (!cur->right) { cur->right = node; break; }
            cur = cur->right;
        }
    }
    return root;
}

JavaScript

var insertIntoBST = function(root, value) {
    var node = new TreeNode(value);
    if (root === null) return node;
    var cur = root;
    while (true) {
        if (value < cur.val) {
            if (cur.left === null) { cur.left = node; break; }
            cur = cur.left;
        } else {
            if (cur.right === null) { cur.right = node; break; }
            cur = cur.right;
        }
    }
    return root;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 189 binary search problems · the whole catalogue

Learn the technique: Binary Search · Binary Trees and Tree Traversals