Insert into a Binary Search Tree

Medium Trees & BST BST Basics Original on LeetCode

Insert into a Binary Search Tree is a medium trees & bst problem solved with the bst basics pattern. The best approach, iterative, runs in O(h) time and O(1) space. Below are 2 approaches in Java, from recursive up.

Problem

Insert val into a binary search tree so that it stays a valid BST, and return the root. The value is guaranteed not to exist in the tree yet.

Examples

Example 1

Input: root = [4, 2, 7, 1, 3], val = 5
Output: [4, 2, 7, 1, 3, 5]
Why: 5 becomes the left child of 7.

Example 2

Input: root = [], val = 8
Output: [8]

Constraints

The tree has 0 to 10^4 nodes; val is not already in the tree.
Any valid BST result is accepted.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Recursive	`O(h)`	`O(h)`
Iterative	`O(h)`	`O(1)`

1Recursive

TimeO(h)

SpaceO(h)

Go left or right like a search. When you reach null, return a new node, and the parent attaches it.

if root == null return new TreeNode(val).
Recurse into the correct side and assign the result to that child.

Java

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;
    }
}

2Iterative

TimeO(h)

SpaceO(1)

Walk down to the parent whose child spot is empty in the right direction and attach the new node there.

If root is null, return a new node.
Loop: pick the side; if that child is null, attach and return root; otherwise move there.

Java

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        TreeNode node = new TreeNode(val);
        if (root == null) return node;
        TreeNode cur = root;
        while (true) {
            if (val < 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;
    }
}

Edge cases to test

Empty tree
Inserting a new minimum or maximum

Hints

Hint 1

Search for val as if it existed; the null spot where the search ends is where it goes.

FAQ

What is the best time complexity for Insert into a Binary Search Tree?

Iterative runs in O(h) time and O(1) extra space.

Which pattern does Insert into a Binary Search Tree use?

It is a trees & bst problem that uses the bst basics pattern. Other problems with the same pattern: Search in a Binary Search Tree, Minimum element in BST.

Is there a brute force solution for Insert into a Binary Search Tree?

Yes. Recursive takes O(h) time and O(h) space. Go left or right like a search.

Which edge cases should I test for Insert into a Binary Search Tree?

Empty tree; Inserting a new minimum or maximum.