binary search tree class - remove, search, insert, remove, and iterator methods - iteration vs recursion

Question

Very recently, I've begun studying and learning about binary trees in java, about their application and how to utilize them. I found this BinaryTree class online and I wanted to implement it:

public abstract class BinaryTree<E> implements Iterable<E> {

protected class Node<T> {

    protected Node(T data) {
        this.data = data;
    }

    protected T data;
    protected Node<T> left;
    protected Node<T> right;
}

public abstract void insert(E data);
public abstract void remove(E data);
public abstract boolean search(E data);

protected Node<E> root;
}

Now, I began simply by creating the header for my header for my implemted class:

public class BinarySearchTree<E extends Comparable<? super E>> extends BinaryTree<E> {

}

And I did the methods one by one, using my programming knowledge. Here is what I ended up creating, and it works perfectly:

import java.util.Iterator;

public class BinarySearchTree<E extends Comparable<? super E>> extends BinaryTree<E> {

private Node<E> findIOP(Node<E> curr) {

    for (curr = curr.left; curr.right != null; curr = curr.right);

    return curr;
}

public void insert(E data) {

    Node<E> temp = new Node<E>(data);

    if (root == null) {
        root = temp;
    }
    else {
        Node<E> curr = root;

        while (true) {
            if (data.compareTo(curr.data) <= 0) {
                if (curr.left != null) {
                    curr = curr.left;
                }
                else {
                    curr.left = temp;
                    break;
                }
            }
            else {
                if (curr.right != null) {
                    curr = curr.right;
                }
                else {
                    curr.right = temp;
                    break;
                }
            }
        }
    }
}

public Iterator<E> iterator() {

    return null;
}

public void remove(E data) {

    if (root != null) {
        if (data.compareTo(root.data) == 0) {
            if (root.left == null || root.right == null) {
                root = root.left != null ? root.left : root.right;
            }
            else {
                Node<E> iop = findIOP(root);
                E temp = root.data;
                root.data = iop.data;
                iop.data = temp;

                if (root.left == iop) {
                    root.left = root.left.left;
                }
                else {
                    Node<E> curr = root.left;
                    while (curr.right != iop) {
                        curr = curr.right;
                    }
                    curr.right = curr.right.left;
                }
            }
        }
        else {
            Node<E> curr = root;
            int cmp;
            while (true) {
                cmp = data.compareTo(curr.data);
                if (cmp < 0 && curr.left != null && data.compareTo(curr.left.data) != 0) {
                    curr = curr.left;
                }
                else if (cmp > 0 && curr.right != null && data.compareTo(curr.right.data) != 0) {
                    curr = curr.right;
                }
                else {
                    break;
                }
            }

            if (cmp < 0 && curr.left != null) {
                if (curr.left.left == null || curr.left.right == null) {
                    curr.left = curr.left.left != null ? curr.left.left : curr.left.right;
                }
                else {
                    Node<E> iop = findIOP(curr.left);
                    E temp = curr.left.data;
                    curr.left.data = iop.data;
                    iop.data = temp;

                    if (curr.left.left == iop) {
                        curr.left.left = curr.left.left.left;
                    }
                    else {
                        Node<E> node = curr.left.left;
                        while (node.right != iop) {
                            node = node.right;
                        }
                        node.right = node.right.left;
                    }
                }
            }
            else if (cmp > 0 && curr.right != null) {
                if (curr.right.left == null || curr.right.right == null) {
                    curr.right = curr.right.left != null ? curr.right.left : curr.right.right;
                }
                else {
                    Node<E> iop = findIOP(curr.right);
                    E temp = curr.right.data;
                    curr.right.data = iop.data;
                    iop.data = temp;

                    if (curr.right.left == iop) {
                        curr.right.left = curr.right.left.left;
                    }
                    else {
                        Node<E> node = curr.right.left;
                        while (node.right != iop) {
                            node = node.right;
                        }
                        node.right = node.right.left;
                    }
                }
            }
        }
    }
}

public boolean search(E data) {

    Node<E> curr = root;

    while (curr != null) {
        if (data.compareTo(curr.data) == 0) {
            return true;
        }
        else if (data.compareTo(curr.data) < 0) {
            curr = curr.left;
        }
        else {
            curr = curr.right;
        }
    }

    return false;
}
}

Feel free to test those methods in a main class if you'd like, they perform their function quite well. However, my concern here is efficiency. After searching online and asking a friend, I learned of something called 'recursion'. Now, almost all of my programming knowledge came via learning Python, and I've never encountered this concept before. I now understand that my solution uses iteration, but I've learned that when it comes to binary trees, iteration is terrible inefficient.

I've tried reading other questions and pages, but I still can't understand recursion well. Can someone explain the concept and show an application of it for the remove, insert, iterator, and search methods in my program? I'm a faster learner, but seeing an application of a concept is what helps me best. Thank you.

Note: Seeing a recursive solution to these functions is really what I'm looking for. I think I've understood the concept, but applying it is where I still have difficulties. I can't exactly apply the concept to the remove, insert, search, and iterator methods here.

Answer 1

The basic idea of recursion is to apply a function to each smaller problem and return the results back up the call stack. For example, in terms of trees, the contains/search method is the result of checking the current node's data, OR the left subtree contains the element, OR the right subtree contains the element. Likewise for insert, compare the Node to the element, then recursively insert right or left and assign a new leaf node as soon as you hit a null node.

In terms of efficiency, recursion has the overhead of placing more calls onto the stacktrace, thus potentially yielding a StackOverflow.

Iteration is often easier to debug because you have an idea of the entire process in each step.

Tail recursion improves efficiency, but I don't think that applies to BinaryTree methods. Either way, both implementations have similar runtime efficiency if written correctly. IMO recursion looks cleaner if the sub-problem is well defined.

---

Here is an example of using recursion to implement a BinaryTree. The remove method was left out for complexity reasons, but I added toString for another example.

public class BinaryTree<E extends Comparable<? super E>> {

    protected class Node<T extends E> {
        protected T data;
        protected Node<T> left;
        protected Node<T> right;

        protected Node(T data) {
            this.data = data;
        }

        protected Node<T> insert(T data) {
            if (data.compareTo(this.data) <= 0) {
                if (left == null) {
                    this.left = new Node(data);
                } else {
                    this.left = this.left.insert(data);
                }
            } else {
                if (right == null) {
                    this.right = new Node(data);
                } else {
                    this.right = this.right.insert(data);
                }
            }

            return this;
        }

        protected boolean search(T data) {
            if (data.compareTo(this.data) == 0) {
                return true;
            }

            if (this.left != null && data.compareTo(this.data) <= 0) {
                return this.left.search(data);
            } else if (this.right != null && data.compareTo(this.data) > 0) {
                return this.right.search(data);
            }

            return false;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            String divider = ", ";

            if (this.left != null) {
                sb.append(this.left.toString()).append(divider);
            }

            sb.append(String.valueOf(this.data)).append(divider);

            if (this.right != null) {
                sb.append(this.right.toString()).append(divider);
            }

            if (sb.length() > divider.length() - 1) {
                sb.setLength(sb.length() - divider.length());
            }

            return sb.toString();
        }
    }

    protected Node<E> root;

    public Node<E> insert(E data) {
        if (root == null) this.root = new Node(data);
        else {
            this.root = this.root.insert(data);
        }
        return this.root;
    }

    public Node<E> remove(E data) {
        return null; // TODO: Implement this
    }

    public boolean search(E data) {
        return root != null && this.root.search(data);
    }

    @Override
    public String toString() {
        return String.valueOf(this.root);
    }
}