Insert (Implementation)

  • Implement the core operations of an OrderedSet efficiently with a Binary Search Tree.

Exercise Complete the implementation of insert.

@Override
public void insert(T t) {
  // TODO Implement Me!
}
Solution

Here is an iterative implementation:

public void insert(T t) {
  if (root == null) { // edge case!
    root = new Node<>(t);
    return;
  }

  Node<T> curr = root;
  while (curr != null) {
    if (curr.data.compareTo(t) > 0) {
      if (curr.left == null) { // reached a leaf
        // insert the new node
        curr.left = new Node<>(t);
        curr = null; // break out of the loop
      } else {
        // explore the left subtree
        curr = curr.left;
      }
    } else if (curr.data.compareTo(t) < 0) {
      if (curr.right == null) { // reached a leaf
        // insert the new node
        curr.right = new Node<>(t);
        curr = null; // break out of the loop
      } else {
        // explore the right subtree
        curr = curr.right;
      }
    } else {
      // duplicate is not allowed!
      return;
    }
  }
}

Here is a recursive implementation of insert

@Override
public void insert(T t) {
  root = insert(root, t);
}

/* inserts given value into subtree rooted at given node
    and returns changed subtree with new node added. */
private Node<T> insert (Node<T> root, T data) {
  if (root == null) {
    /* If the tree is empty, return a new node */
    return new Node<>(data);
  }

  /* Otherwise, recur down the tree */
  if (root.data.compareTo(data) > 0) {
    root.left = insert(root.left, data);
  } else if (root.data.compareTo(data) < 0) {
    root.right = insert(root.right, data);
  }

  /* return the (unchanged) node pointer */
  return root;
}

Note the use of recursion for insert — using the value returned to update the current node. This may take a moment to understand!