Insert into a Binary Search Tree

medium tree bst

Problem

Given the root of a binary search tree and a value to insert, return the root after inserting the value. Any valid BST structure that contains the inserted value is acceptable; you do not need to balance.

Inputroot = [4,2,7,1,3], val = 5

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

5 lands as the left child of 7.

tree (level-order BST, "null" for empty)

val

def insert(root, val):
    if not root: return TreeNode(val)
    cur = root
    while True:
        if val < cur.val:
            if not cur.left: cur.left = TreeNode(val); break
            cur = cur.left
        else:
            if not cur.right: cur.right = TreeNode(val); break
            cur = cur.right
    return root

function insertIntoBST(root, val) {
  if (!root) return { val, left: null, right: null };
  let cur = root;
  while (true) {
    if (val < cur.val) {
      if (!cur.left) { cur.left = { val, left: null, right: null }; break; }
      cur = cur.left;
    } else {
      if (!cur.right) { cur.right = { val, left: null, right: null }; break; }
      cur = cur.right;
    }
  }
  return root;
}

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

TreeNode* insertIntoBST(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    TreeNode* cur = root;
    while (true) {
        if (val < cur->val) {
            if (!cur->left) { cur->left = new TreeNode(val); break; }
            cur = cur->left;
        } else {
            if (!cur->right) { cur->right = new TreeNode(val); break; }
            cur = cur->right;
        }
    }
    return root;
}

Explanation

To add a value to a BST, we just follow the same search path we would use to look it up. When that search falls off the tree into an empty spot, that empty spot is exactly where the new value belongs as a leaf.

Why does this work? In a BST every value smaller than a node lives to its left and every larger value to its right. So comparing val against each node tells us which way to go, and the first empty child we hit is the only correct place to keep the ordering intact.

The code keeps a cur pointer and loops: if val < cur.val it moves left (or drops the new node into cur.left if empty), otherwise it moves right. We never need to rearrange existing nodes, and an empty tree just returns a fresh node.

Example: root = [4,2,7,1,3], val = 5. Start at 4: 5 ≥ 4 go right to 7. At 7: 5 < 7 go left, but 7.left is empty, so 5 becomes the left child of 7.

Since we only walk one root-to-leaf path, the cost is O(h) time with O(1) extra space in this iterative version.

Time: O(h) Space: O(1) iterative