Add a New Key to a Search Tree

Medium20–25 min

Topics

Binary Search TreeBSTInsertionIteration

Companies

AmazonMicrosoftAdobeOracleFlipkart

You are given the root of a binary search tree with distinct values and a key that is not yet in the tree. Insert the key as a new leaf, at the position where a search for the key would have ended, so the tree remains a valid binary search tree. Every existing node keeps its place. Return the root of the resulting tree.

You could rebuild the whole tree from a list of its values, but a single walk down the search path finds the empty slot directly.

Test Case 1:

Input:root = [45, 25, 65, 15, 35, 55, 75], key = 40

Output:[45, 25, 65, 15, 35, 55, 75, null, null, null, 40]

Explanation:40 < 45 → left; 40 > 25 → right (35); 40 > 35 → right, which is empty. So 40 becomes the right child of 35.

Test Case 2:

Input:root = [45, 25, 65, 15, 35, 55, 75], key = 5

Output:[45, 25, 65, 15, 35, 55, 75, 5]

Explanation:5 goes left all the way down and becomes the left child of 15.

Test Case 3:

Input:root = [], key = 8

Output:[8]

Explanation:Inserting into an empty tree creates the root.

Constraints

◆0 ≤ number of nodes ≤ 100; all node values are distinct, 0 ≤ node.val ≤ 1000
◆The tree is a binary search tree (left subtree smaller, right subtree larger at every node), given by its root node (null for an empty tree)
◆key is a value between 0 and 1000 that is NOT already in the tree
◆Insert key as a NEW LEAF at the position where a search for it would have ended, keeping every other node where it is. Return the root of the resulting tree (checked as a level-order list)

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Collect All Values, Add the Key, Rebuild the Tree

Brute

List the tree's values in pre-order (parents before children), append the new key, and build a fresh tree by inserting the values one at a time in that order. Inserting in pre-order reproduces exactly the same shape, and the key, inserted last, lands where a search for it ends — so the result is correct. But every existing node is re-created and re-inserted, costing O(n · h) time and O(n) extra space, when only one new leaf was needed.

TimeO(n · h)

SpaceO(n)

Java

Try it out

class Solution {
    public TreeNode insertKey(TreeNode root, int key) {
        List<Integer> order = new ArrayList<>();
        preorder(root, order);
        order.add(key);
        TreeNode result = null;
        for (int v : order) result = insertOne(result, v);
        return result;
    }

    private void preorder(TreeNode node, List<Integer> order) {
        if (node == null) return;
        order.add(node.val);
        preorder(node.left, order);
        preorder(node.right, order);
    }

    private TreeNode insertOne(TreeNode node, int v) {
        if (node == null) return new TreeNode(v);
        if (v < node.val) node.left = insertOne(node.left, v);
        else node.right = insertOne(node.right, v);
        return node;
    }
}

Optimal — Walk Down and Attach the New Leaf

Optimal

Create the new node, then walk down from the root exactly like a search for the key: go left if the key is smaller than the current node, right otherwise. The first time the child you want to step into is empty, attach the new node there and stop — nothing else moves. An empty tree simply returns the new node as the root. Only one root-to-leaf path is followed: O(h) time (O(log n) when balanced) and O(1) extra space besides the new node.

TimeO(h)

SpaceO(1)