Insert into a Binary Search Tree — Practice

Problem

Given the root of a BST and a value to insert, insert the value into the BST and return the root of the resulting tree. There may be multiple valid trees — return any of them that preserves the BST property.

Examples

Example 1

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

Output: [4,2,7,1,3,5]

Explanation: 5 > 4, go right to 7; 5 < 7, go left — 7 has no left child, so 5 is attached there.

Constraints

•1 <= number of nodes <= 10^4
•-10^8 <= Node.val, val <= 10^8
•All values are unique

Hints

Hint 1

A BST's sorted-order property tells you exactly which direction to go at every node — no need to search both subtrees.

Hint 2

The insertion point is always a leaf position — you're not rearranging the tree, just attaching one new node where a null child currently is.

Solutions

public TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null) return new TreeNode(val); // found the correct empty spot
    if (val < root.val) {
        root.left = insertIntoBST(root.left, val);
    } else {
        root.right = insertIntoBST(root.right, val);
    }
    return root;
}

Time: O(h), h = tree height (O(log n) balanced, O(n) worst case) · Space: O(h)