A Binary Search Tree implementation that demonstrates some functional paradigms.

BinaryST.java

/**
 * This file has been modified slightly for public release.
 * Some documentation has been removed.
 */

import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.function.Function;

public class BinaryST<E extends Comparable<E>> {

    private Node<E> root;
    private int size;

    public BinaryST() {
        this.root = null;
    }

    /**
     * Searches for a given data value in this tree.
     * @return a Node.
     */
    private Node<E> search(E target) {
        return search(target, root);
    }

    /**
     * Searches for a given data value in a subtree.
     * @return a Node.
     */
    private Node<E> search(E target, Node<E> subtree) {
        Node<E> current = subtree;
        while (current != null) {
            int comparison = target.compareTo(current.data);
            if (comparison == 0)
                return current;
            
            if (comparison < 0)
                current = current.left;
            else
                current = current.right;
        }
        return null;
    }

    /**
     * Performs an in-order traversal of the tree represented by a given node.
     * @param node the node to begin traversal from
     * @param callback a function called for each node in the traversal. If the
     * callback returns false, the traversal is aborted.
     */
    private boolean traverseIn(Node<E> node, Function<Node<E>, Boolean> callback) {
        if (node == null)
            return true;

        if (!traverseIn(node.left, callback))
            return false;
        if (!callback.apply(node))
            return false;
        if (!traverseIn(node.right, callback))
            return false;

        return true;
    }

    /**
     * Performs a reverse in-order traversal of the tree represented by a given node.
     * @param node the node to begin traversal from
     * @param callback a function called for each node in the traversal. If the
     * callback returns false, the traversal is aborted.
     */
    private boolean traverseInReverse(Node<E> node, Function<Node<E>, Boolean> callback) {
        if (node == null)
            return true;

        if (!traverseInReverse(node.right, callback))
            return false;
        if (!callback.apply(node))
            return false;
        if (!traverseInReverse(node.left, callback))
            return false;

        return true;
    }


    /**
     *  Add the specified item to this Binary Search Tree if it is not already present.
     *  @param value the value to add to the tree
     *  @return false if an item equivalent to value is already present
     *  in the tree, return true if value is added to the tree and size() = old size() + 1
     */
    public boolean add(E value) {
        if (value == null)
            throw new IllegalArgumentException("Cannot add null.");

        Node<E> node = new Node<E>(value);
        boolean added = true;
        
        if (root == null)
            root = node;
        else
            added = add(root, node);
        
        if (added)
            size++;
        return added;
    }


    /**
     * Recursive step for node add.
     * Called by add(E value).
     * @param current the current node being searched
     * @param node the node being inserted
     */
    private boolean add(Node<E> current, Node<E> node) {
        int comparison = node.data.compareTo(current.data);
        
        //base case: cannot insert node
        if (comparison == 0) {
            return false;
        }

        //inserted data is less than data of current node
        else if (comparison < 0) {
            if (current.left != null)
                return add(current.left, node);
            current.left = node;
            return true;
        }

        //inserted data is greater than data of current node
        else {
            if (current.right != null)
                return add(current.right, node);
            current.right = node;
            return true;
        }
    }


    /**
     * [removed]
     * Removes an item from the tree.
     */
    public boolean remove(E value) {
        if (value == null)
            throw new IllegalArgumentException("Cannot remove null.");

        boolean removed = remove(value, root, null);
        if (removed)
            size--;
        return removed;
    }

    /**
     * Recursive step for node removal.
     * @param value the value to search for
     * @param subtree the subtree in which to search
     * @param parent the parent of the subtree
     * @return whether the remove was successful
     */
    private boolean remove(E value, Node<E> subtree, Node<E> parent) {
        if (subtree == null)
            return false;

        int comparison = value.compareTo(subtree.data);
        
        if (comparison == 0)
            return removeNode(subtree, parent);
        else if (comparison < 0)
            return remove(value, subtree.left, subtree);
        else
            return remove(value, subtree.right, subtree);
    }

    /**
     * Removes a given from its parent.
     * Recursively calls remove() if necessary.
     * @param node the node to remove
     * @param parent the parent of node
     * @return whether the remove was successful.
     */
    private boolean removeNode(Node<E> node, Node<E> parent) {
        //two children
        if (node.left != null && node.right != null) {
            //replace this node's data with largest data in its left subtree
            Value<E> maxOfLeft = new Value<>(null);
            traverseInReverse(node.left, n -> {
                maxOfLeft.value = n.data;
                return false;
            });
            node.data = maxOfLeft.value;

            //recursively remove the duplicate value from the left subtree
            return remove(node.data, node.left, node);
        }
        else {
            Node<E> replaceWith;
            
            //one child
            if (node.left != null || node.right != null)
                replaceWith = node.left != null ? node.left : node.right;
            //no children
            else
                replaceWith = null;

            if (parent == null)
                root = replaceWith;
            else if (parent.left == node)
                parent.left = replaceWith;
            else
                parent.right = replaceWith;
        }
        return true;
    }


    /**
     * [removed]
     * Determines whether a node is present in this tree.
     */
    public boolean isPresent(E value) {
        if (value == null)
            throw new IllegalArgumentException("Cannot search for null.");

        return search(value) != null;
    }


    /**
     * [removed]
     * Determines the number of elements in this tree.
     */
    public int size() {
        return size;
    }


    /**
     * [removed]
     * Returns the height of this tree
     */
    public int height() {
        return height(root, 0);
    }

    /**
     * Recursive step for height calculation
     * @param node node to check height of
     * @param h current height
     * @return height of the subtree represented by node
     */
    public int height(Node<E> node, int h) {
        if (node == null)
            return h-1;
        return Math.max(height(node.left, h+1), height(node.right, h+1));
    }


    /**
     * [removed]
     * Gets a list of all elements in this tree
     */
    public List<E> getAll() {
        List<E> out = new ArrayList<E>();
        traverseIn(root, node -> out.add(node.data));
        return out;
    }


    /**
     * [removed]
     * Gets the maximum value in this tree.
     */
    public E max() {
        if (size() <= 0)
            throw new IllegalArgumentException("Tree is empty.");

        Value<E> max = new Value<>(null);

        //the first node in a reverse in-order traversal is the largest
        traverseInReverse(root, node -> {
            max.value = node.data;
            return false;
        });
        return max.value;
    }


    /**
     * [removed]
     * Gets the minimum value in this tree.
     */
    public E min() {
        if (size() <= 0)
            throw new IllegalArgumentException("Tree is empty.");

        Value<E> min = new Value<>(null);

        //the first node in an in-order traversal is the smallest
        traverseIn(root, node -> {
            min.value = node.data;
            return false;
        });
        return min.value;
    }


    /**
     * [removed]
     * An iterative version of the add method.
     */
    public boolean addIterative(E data) {
        if (data == null)
            throw new IllegalArgumentException("Cannot add null.");

        //special case: no root
        if (root == null) {
            root = new Node<E>(data);
            size++;
            return true;
        }

        Node<E> current = root, parent = null;
        while (current != null) {
            int comparison = data.compareTo(current.data);
            if (comparison == 0)
                return false;
            
            //inserted element is larger; go right
            if (comparison > 0) {
                if (current.right == null) {
                    current.right = new Node<E>(data);
                    size++;
                    return true;
                }
                current = current.right;
            }

            //inserted element is smaller; go left
            else {
                if (current.left == null) {
                    current.left = new Node<E>(data);
                    size++;
                    return true;
                }
                current = current.left;
            }
        }
        return false;
    }


    /**
     * [removed]
     * Gets the kth element in the in-order traversal of this tree.
     */
    public E get(int kth) {
        if (kth < 0 || kth >= size())
            throw new IllegalArgumentException("Get index out of bounds: "+kth);

        Value<Integer> k = new Value<>(0);
        Value<E> item = new Value<>(null);

        //increment counter until kth node is reached
        traverseIn(root, node -> {
            if (k.value++ == kth) {
                //record data of kth node and stop traversal
                item.value = node.data;
                return false;
            }
            return true;
        });
        return item.value;
    }


    /**
     * [removed]
     * Returns a list of all elements in the tree less than a given value
     */
    public List<E> allLessThan(E value) {
        if (value == null)
            throw new IllegalArgumentException("Cannot search for null.");

        List<E> out = new ArrayList<>();
        
        //in-order traversal visits smallest nodes first
        traverseIn(root, node -> {
            //stop traversal when a larger node is reached
            if (node.data.compareTo(value) >= 0)
                return false;
            out.add(node.data);
            return true;
        });
        return out;
    }


    /**
     * [removed]
     * Returns a list of all elements in the tree greater than a given value
     */
    public List<E> allGreaterThan(E value) {
        if (value == null)
            throw new IllegalArgumentException("Cannot search for null.");

        LinkedList<E> out = new LinkedList<>();

        //reverse in-order traversal visits largest nodes first
        traverseInReverse(root, node -> {
            //stop traversal when a larger node is reached
            if (node.data.compareTo(value) <= 0)
                return false;
            out.addFirst(node.data);
            return true;
        });

        return out;
    }


    /**
     * [removed]
     * Counts the number of Nodes that are at a given depth
     */
    public int nodesAtDepth(int d) {
        return nodesAtDepth(d, root, 0);
    }

    /**
     * Find the number of nodes in a subtree at the specified depth.
     * @param d target depth
     * @param node current subtree
     * @param current current depth
     * @return number of nodes in subtree at depth d
     */
    private int nodesAtDepth(int d, Node<E> node, int current) {
        //base case: completed branch
        if (node == null)
            return 0;
        
        //base case: reached depth
        if (current++ == d)
            return 1;
        
        //recursive case: consider left and right children
        return nodesAtDepth(d, node.left, current) +
               nodesAtDepth(d, node.right, current);
    }

    /**
     * Represents a value of any type.
     * Java lambdas are not closures, so they may not modify local variables.
     * However, they may modify things on the heap, e.g. fields of an object
     * instance.
     */
    private static class Value<T> {
        T value;
        Value(T value) {
            this.value = value;
        }
    }

    private static class Node<E extends Comparable<E>> {
        private E data;
        private Node<E> left;
        private Node<E> right;

        public Node() {
            this(null);
        }

        public Node(E val) {
            this(null, val, null); 
        }

        public Node(Node<E> left, E val, Node<E> right) {
            this.data = val;
            this.left = left;
            this.right = right;
        } 
    }
}