Command Palette

Search for a command to run...

Hectal
Problem 17.2 · Binary Search TreesMedium

Insert into a Binary Search Tree

PatternBST Ordering

What it teaches: Insert = search until you fall off, then attach a leaf.

Practise it on judges as “Insert into a Binary Search Tree”.

The problem

Insert val (not already in the tree) as a new leaf and return the root.

Example 1

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

Constraints

  • 0 ≤ nodes ≤ 10⁴
  • val is not in the tree

Pattern clues in the wording

  • → Add to a BST without restructuring

These clues point to BST Ordering: Use left < node < right to skip half the tree, and in-order traversal to visit values in sorted order.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        return root;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
root = [4,2,7,1,3]
val = 5
[4,2,7,1,3,5]
2
root = [40,20,60,10,30,50,70]
val = 25
[40,20,60,10,30,50,70,null,null,25]
3
root = []
val = 5
[5]

From slow to fast

Approaches

1. Recursive insert · O(h)
1

Recursive insert

Time O(h) Space O(h)

insert(n): null → new node. Smaller → n.left = insert(n.left). Larger → n.right = insert(n.right). Return n.

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

Verdict: Short and clear.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Empty tree
  • New minimum or maximum

Mistakes people make

  • Forgetting to reassign the child pointer with the returned node.

Interview

Follow-up questions

Why do sorted inserts hurt?