☕ DSA Java Articles

Topics › Binary Search Trees › Practice Problems

Insert a given node in BST

Medium TUF ID 104 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the root of a binary search tree and a value val that is not already in the tree. Insert val so that the tree is still a BST, and return the root of the resulting tree. Several valid trees may exist; the standard answer, and the one produced here, adds val as a new leaf and leaves every existing link in place.

Constraints: up to 10^4 nodes; all keys and val are distinct and fit in an int.

Example 1

        4                      4
       / \                    / \
      2   7       val = 5    2   7
     / \                    / \  /
    1   3                  1  3 5

5 > 4, so it belongs right of the root; 5 < 7, so it belongs left of 7, which is an empty slot. Output in level order: [4, 2, 7, 1, 3, 5].

Example 2

root = [40, 20, 60, 10, 30, 50, 70], val = 25
answer = [40, 20, 60, 10, 30, 50, 70, null, null, 25]

25 < 40 goes left, 25 > 20 goes right, 25 < 30 goes left, which is empty: 25 becomes the left child of 30.

Why the new key belongs at the end of its search path

Search for val as if it were in the tree. Since it is not, the search ends by stepping into an empty child slot. Put the new node exactly there.

This keeps the BST property for every node. Take any ancestor a on the path. We went left at a exactly when val < a.val, so the new node lands in the left subtree of a only when it is smaller, and in the right subtree only when it is larger. Every constraint along the path is satisfied. Nodes that are not on the path do not get a new descendant, so their constraints are unaffected. Nothing else in the tree moves.

It is also the only place a leaf can go: any other empty slot is in a subtree that some comparison on the path ruled out.

There is no meaningful brute force here. One could collect all keys, add val and rebuild a tree from scratch in O(n), but that discards the structure for no gain. The two approaches below are the same walk written two ways.

Approach 1: Recursive descent

Intuition. Let the function mean “insert val into this subtree and return the subtree’s root”. For an empty subtree, the answer is a brand-new node. For a non-empty one, insert into the correct side and reattach the result as that child. On every level except the bottom, the reattachment writes back the same child it already had; at the bottom it links in the new node. The same rule also handles an empty tree: the new node becomes the root and is returned.

Algorithm.

  1. If root is null, return new TreeNode(val).
  2. If val < root.val, set root.left = recursive(root.left, val).
  3. Otherwise set root.right = recursive(root.right, val).
  4. Return root.
static TreeNode recursive(TreeNode root, int val) {
    if (root == null) return new TreeNode(val);      // fell off the tree: this empty spot is where val belongs
    if (val < root.val) root.left = recursive(root.left, val);
    else root.right = recursive(root.right, val);
    return root;
}

Complexity. Time O(h): one call per level of the search path. Space O(h) for the recursion stack, where h is the height.

Approach 2: Optimal, iterative descent

Intuition. The loop has to stop one step earlier than a plain search. A search moves cur until it becomes null, but by then the parent is lost, and the parent is the node whose child link we must set. So at each node we look at the child we are about to move to: if it is empty, link the new node there and stop; otherwise move to it.

Algorithm.

  1. Create node = new TreeNode(val). If root is null, return node.
  2. Set cur = root and loop:
    • if val < cur.val: if cur.left is empty, set cur.left = node and stop; otherwise move left;
    • else: if cur.right is empty, set cur.right = node and stop; otherwise move right.
  3. Return root, which has not changed.
static TreeNode optimal(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;
}

Dry run on Example 2 (val = 25):

cur comparison child on that side action
40 25 < 40 left = 20 move to 20
20 25 > 20 right = 30 move to 30
30 25 < 30 left = null link 25 as left child, stop

Complexity. Time O(h), Space O(1). The while (true) loop always terminates: each iteration moves one level down, and the tree has finite height, so an empty slot is reached after at most h steps.

Repeated insertion and tree shape

Inserting keys one by one is the standard way to build a BST, and the final shape depends entirely on the order. The Java file inserts a fixed permutation of 1..100 with both methods, checks that they produce the identical tree, and checks that its inorder traversal is exactly 1, 2, ..., 100. If the keys had arrived in sorted order instead, every insertion would go right at every node and the result would be a chain of height 100, where every later operation costs O(n). Self-balancing trees (AVL, red-black) add rotations after each insertion to prevent that; plain leaf insertion does not.

Edge cases and pitfalls