2.2 Insert in BST

Assumption: No duplicate keys in BST. If the target already existed in BST, do nothing

Input: TreeNode root, int target

Output: TreeNode new tree with target node inserted

Corner case: if root == null, insert

Solution 1: Iterative checking on root p's children

1. Stop condition: when cur.key == target

2. Case 1: If cur.key > target, go check on cur.left if not null, else insert, break

Case 2: if cur.key < target, go check on cur.right if not null, else insert, break

public TreeNode insert(TreeNode root, int target) {
  if (root == null) {
    return new TreeNode(target);
  }
  TreeNode cur = root;
  while (cur.key != target) {
    if (cur.key > target) {
      if (cur.left != null) {
        cur = cur.left;
      } else {
        cur.left = new TreeNode(target);
        break;
      }
    } else {
      if (cur.right != null) {
        cur = cur.right;
      } else {
        cur.right = new TreeNode(target);
        break;
      }
    }
  }
  return root;
}

Solution 2: Iterative checking back on root's parent

1. Stop condition: when root != null

2. same two cases, but also check pre.key < or > target

public TreeNode insert(TreeNode root, target) {
  if (root == null) {
    return new TreeNode(target);
  }
  TreeNode returnRoot = root;
  TreeNode pre = null;
  while (root != null) {
    pre = root;
    if (root.key < target) {
      root = root.right;
    } else if (root.key > target) {
      root = root.left;
    } else {
      return returnRoot;
    }
  } //should have found the parent of which we could insert under
  if (pre.key < target) {
    pre.right = new TreeNode(target);
  } else if (pre.key > target) {
    pre.left = new TreeNode(target);
  }
  return returnRoot;
}

Solution 3: Recursive, return new root

1. Base case: root == null, insert

2. Case 1: if root.key < target, go to root.right and call

Case 2: if root.key > target, go to root.left and call

3. return root

public TreeNode insert(TreeNode root, int target) {
  if (root == null) { return new TreeNode(target); }
  if (root.key < target) { 
    return root.left = insert(root.left, target); 
  } else if (root.key > target) { 
    return root.right = insert(root.right, target); 
  }
  return root;
}