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!