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, Python, C++ and JavaScript, 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.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

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.

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 code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
RecursiveO(h)O(h)
IterativeO(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.

  1. if root == null return new TreeNode(val).
  2. Recurse into the correct side and assign the result to that child.
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.

  1. If root is null, return a new node.
  2. Loop: pick the side; if that child is null, attach and return root; otherwise move there.
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, Binary Search Tree Iterator.

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.