Insert into a Binary Search Tree

MEDIUM✓ CHIP-TIMEDLC #701 — FULL STATEMENT ↗

The drill: Add a new value into a binary search tree so the search-tree ordering still holds afterward — the value is new, and any valid placement is fine, but there's exactly one place a plain search lands.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A binary search tree and a new value arrive together, and the task is to add that value into the tree while keeping the search-tree ordering intact everywhere.

The value being inserted is guaranteed not to already exist in the tree, and because a BST can place a new leaf in more than one structurally valid spot, any tree that both keeps the ordering correct and includes the new value counts as a right answer.

The tree may start out completely empty, in which case the new value simply becomes the root of a brand-new single-node tree.

EX 01

root = [] · val = 5

→ [5]

INSERTING INTO AN EMPTY TREE

EX 02

root = [5] · val = 2

→ [5, 2]

SINGLE NODE, GOES LEFT

EX 03

root = [5] · val = 9

→ [5, null, 9]

SINGLE NODE, GOES RIGHT

the value being inserted is not already present in the tree
the tree can hold anywhere from zero to a few thousand nodes before insertion
all values in the tree are unique and follow standard BST ordering
any structurally valid placement of the new value is accepted

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A BST already tells you where a value belongs: smaller goes left, larger goes right, at every node you visit. Follow that rule until you fall off the tree — that empty spot is where the new node goes.

HINT 2 THE STRUCTURE

Recursively: at each node, recurse into whichever child side the value belongs on, then reattach whatever comes back as that child. An empty spot (null) is the base case — that's where a fresh node is created.

HINT 3 ONE STEP FROM THE ANSWER

No return-value plumbing needed if you walk it instead: step down comparing the value at each node, and the instant the correct-side child is missing, attach the new node there directly.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE FALL-OFF SPOTPATTERN · ITERATIVE WALKroot = [8, 3, 10] · val = 1

STEP 1

Insert 1 into this BST: walk down comparing at each step, and the instant the correct-side child is empty, attach the new node there.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/insert-into-a-binary-search-tree.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root:
            return TreeNode(val)
        curr = root
        while True:
            if val < curr.val:
                if curr.left is None:
                    curr.left = TreeNode(val)
                    break
                curr = curr.left
            else:
                if curr.right is None:
                    curr.right = TreeNode(val)
                    break
                curr = curr.right
        return root

TIME O(H)SPACE O(1)PYTHON · RACE PACE · 17 LN

class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root:
            return TreeNode(val)
        if val < root.val:
            root.left = self.insertIntoBST(root.left, val)
        else:
            root.right = self.insertIntoBST(root.right, val)
        return root

TIME O(H)SPACE O(H)PYTHON · TRAINING PACE · 9 LN

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        TreeNode curr = root;
        while (true) {
            if (val < curr.val) {
                if (curr.left == null) {
                    curr.left = new TreeNode(val);
                    break;
                }
                curr = curr.left;
            } else {
                if (curr.right == null) {
                    curr.right = new TreeNode(val);
                    break;
                }
                curr = curr.right;
            }
        }
        return root;
    }
}

TIME O(H)SPACE O(1)JAVA · RACE PACE · 24 LN

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

TIME O(H)SPACE O(H)JAVA · TRAINING PACE · 13 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED