Doing tree search in Java

Question

I have this tiny library for building unbalanced, binary trees and doing tree search on them. I tried hard to define a generic API that would allow custom implementations of trees.

AbstractBinaryTreeNode.java:

package net.coderodde.graph.tree;
/**
 * This class defines the API for a binary tree node.
 * 
 * @author Rodion Efremov
 * @version 1.6
 * @param <E> the type of satellite data.
 * @param <N> the actual node implementation type.
 */
public abstract class
 AbstractBinaryTreeNode<E extends Comparable<? super E>, 
 N extends AbstractBinaryTreeNode<E, N>> {
 /**
 * Stores the satellite datum of this node.
 */
 protected final E element;
 /**
 * The left child node.
 */
 protected N left;
 /**
 * The right child node.
 */
 protected N right;
 /**
 * Constructs a new binary tree node with <code>element</code> as the 
 * satellite datum.
 * 
 * @param element the satellite datum.
 */
 public AbstractBinaryTreeNode(final E element) {
 checkNotNull(element);
 this.element = element;
 }
 /**
 * Returns the element of this node.
 * 
 * @return the element of this node.
 */
 public E getElement() {
 return element;
 }
 /**
 * Returns the left child node.
 * 
 * @return the left child node.
 */
 public N getLeft() {
 return left;
 }
 /**
 * Returns the right child node.
 * 
 * @return the right child node.
 */
 public N getRight() {
 return right;
 }
 /**
 * Checks that the input element is not <code>null</code>.
 * 
 * @param element the element to check.
 */
 private void checkNotNull(final E element) {
 if (element == null) {
 throw new NullPointerException(
 "The element for a " + getClass().getSimpleName() + 
 " is null.");
 }
 }
}

AbstractTreeNodeFinder.java:

package net.coderodde.graph.tree;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.function.Predicate;
/**
 * This abstract class defines the API for tree search algorithms.
 * 
 * @author Rodion Efremov
 * @version 1.6
 * @param <N> the type of nodes being searched.
 */
public abstract class 
 AbstractTreeNodeFinder<N extends AbstractBinaryTreeNode<?, N>>
{
 /**
 * Initiates the search from <code>source</code> and stops the search at 
 * a node which passes the input predicate. The path from 
 * <code>source</code> to the goal node is returned. If the goal node is 
 * not reachable, an empty list is returned.
 * 
 * @param source the source state.
 * @param goalNodePredicate the predicate for recognizing goal nodes.
 * @return the list describing a path from a source to a goal node.
 */
 public abstract List<N> search(final N source,
 final Predicate<N> goalNodePredicate);
 /**
 * Constructs a shortest path.
 * 
 * @param goal the goal node.
 * @param parentMap the map mapping a node to its parent node in the tree.
 * @return a path.
 */
 protected List<N> tracebackPath(final N goal, final Map<N, N> parentMap) {
 final List<N> path = new ArrayList<>();
 N current = goal;
 while (current != null) {
 path.add(current);
 current = parentMap.get(current);
 }
 Collections.<N>reverse(path);
 return path;
 }
}

BinaryTree.java:

package net.coderodde.graph.tree;
/**
 * This class implements a simple, unbalanced binary tree.
 * 
 * @author Rodion Efremov
 * @version 1.6
 * @param <E> the type of satellite data.
 */
public class BinaryTree<E extends Comparable<? super E>> {
 /**
 * This class holds the actual satellite datum and possible links to child
 * tree nodes. This inner static class is declared public so that other 
 * algorithms can work on them.
 * 
 * @param <E> the type of the satellite datum.
 */
 public static final class BinaryTreeNode<E extends Comparable<? super E>> 
 extends AbstractBinaryTreeNode<E, BinaryTreeNode<E>> {
 /**
 * Construct a new tree node with given element.
 * 
 * @param element the element to store in this tree node.
 */
 BinaryTreeNode(final E element) {
 super(element);
 }
 /**
 * Returns the satellite datum of this tree node.
 * 
 * @return the satellite datum.
 */
 public E getElement() {
 return element;
 }
 }
 /**
 * The root node of this tree.
 */
 private BinaryTreeNode<E> root;
 /**
 * Adds a new element to this tree.
 * 
 * @param element the element to add. 
 */
 public void add(final E element) {
 if (root == null) {
 root = new BinaryTreeNode<>(element);
 return;
 }
 BinaryTreeNode<E> parent = null;
 BinaryTreeNode<E> current = root;
 while (current != null) {
 parent = current;
 current = element.compareTo(current.element) < 0 ?
 current.left :
 current.right;
 }
 if (element.compareTo(parent.element) < 0) {
 parent.left = new BinaryTreeNode<>(element);
 } else {
 parent.right = new BinaryTreeNode<>(element);
 }
 }
 /**
 * Returns the root node of this tree.
 * 
 * @return the root node.
 */
 public BinaryTreeNode<E> getRoot() {
 return root;
 }
 /**
 * Returns the node containing <code>element</code> or <code>null</code> if
 * there is no such node.
 * 
 * @param element the target element.
 * @return the tree node or <code>null</code>.
 */
 public BinaryTreeNode<E> getNode(final E element) {
 BinaryTreeNode<E> current = root;
 while (current != null) {
 if (current.getElement().equals(element)) {
 return current;
 }
 current = element.compareTo(current.getElement()) < 0 ?
 current.left :
 current.right;
 }
 return null;
 }
}

BreadthFirstSearchNodeFinder.java:

package net.coderodde.graph.tree.support;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.function.Predicate;
import net.coderodde.graph.tree.AbstractBinaryTreeNode;
import net.coderodde.graph.tree.AbstractTreeNodeFinder;
/**
 * This class implements breadth-first search for trees.
 * 
 * @author Rodion Efremov
 * @version 1.6
 * @param <N> the actual binary tree node type.
 */
public class BreadthFirstSearchNodeFinder<N extends AbstractBinaryTreeNode<?, N>>
extends AbstractTreeNodeFinder<N> {
 /**
 * Searches for a shortest path in a binary tree using breadth-first search.
 * 
 * @param source the source node.
 * @param goalNodePredicate the goal node predicate.
 * @return the path from <code>source</code> to a goal 
 * node.
 */ 
 @Override
 public List<N> search(final N source, 
 final Predicate<N> goalNodePredicate) {
 if (source == null) {
 // 'path' is empty, thus denoting a non-existent path.
 return new ArrayList<>(0);
 }
 final Deque<N> queue = new ArrayDeque<>();
 final Map<N, N> parentMap = new HashMap<>();
 queue.addLast(source);
 parentMap.put(source, null);
 while (!queue.isEmpty()) {
 final N current = queue.poll();
 if (goalNodePredicate.test(current)) {
 return tracebackPath(current, parentMap);
 }
 final N left = current.getLeft();
 final N right = current.getRight();
 if (left != null) {
 queue.addLast(left);
 parentMap.put(left, current);
 }
 if (right != null) {
 queue.addLast(right);
 parentMap.put(right, current);
 }
 }
 return new ArrayList<>();
 }
}

DepthFirstSearchNodeFinder.java:

package net.coderodde.graph.tree.support;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.function.Predicate;
import net.coderodde.graph.tree.AbstractBinaryTreeNode;
import net.coderodde.graph.tree.AbstractTreeNodeFinder;
/**
 * This class implements a depth-first search for finding paths from source 
 * nodes to goal nodes.
 * 
 * @author Rodion Efremov
 * @version 1.6
 * @param <N> the actual type of a tree node.
 */
public class DepthFirstSearchNodeFinder<N extends AbstractBinaryTreeNode<?, N>>
extends AbstractTreeNodeFinder<N> {
 /**
 * Searches for a shortest path from <code>source</code> to any node 
 * satisfying the <code>goalNodePredicate</code>.
 * 
 * @param source the source node.
 * @param goalNodePredicate the goal node predicate.
 * @return a path.
 */
 @Override
 public List<N> search(final N source, 
 final Predicate<N> goalNodePredicate) {
 if (source == null) {
 // 'path' is empty, thus denoting a non-existent path.
 return new ArrayList<>(0);
 }
 int bestLength = Integer.MAX_VALUE;
 List<N> shortestPath = new ArrayList<>();
 final Deque<N> stack = new ArrayDeque<>();
 final Map<N, N> parentMap = new HashMap<>();
 stack.addLast(source);
 parentMap.put(source, null);
 while (!stack.isEmpty()) {
 final N current = stack.removeLast();
 if (goalNodePredicate.test(current)) {
 final List<N> path = tracebackPath(current, parentMap);
 if (bestLength > path.size()) {
 bestLength = path.size();
 shortestPath = path;
 }
 }
 final N left = current.getLeft();
 final N right = current.getRight();
 if (left != null) {
 stack.addLast(left);
 parentMap.put(left, current);
 }
 if (right != null) {
 stack.addLast(right);
 parentMap.put(right, current);
 }
 }
 return shortestPath;
 }
}

IDDFSNodeFinder.java:

package net.coderodde.graph.tree.support;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.function.Predicate;
import net.coderodde.graph.tree.AbstractBinaryTreeNode;
import net.coderodde.graph.tree.AbstractTreeNodeFinder;
/**
 * This class implements the IDDFS algorithm (iterative deepening depth-first
 * search) described in 
 * <a href="http://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search">Wikipedia</a>.
 * 
 * @author Rodion Efremov
 * @version 1.6
 * @param <N> the actual type of a tree node.
 */
public class IDDFSNodeFinder<N extends AbstractBinaryTreeNode<?, N>> 
extends AbstractTreeNodeFinder<N> {
 private int previousReachedNodes;
 private int reachedNodes;
 @Override
 public List<N> search(final N source, 
 final Predicate<N> goalNodePredicate) {
 if (source == null) {
 // 'path' is empty, thus denoting a non-existent path.
 return new ArrayList<>(0);
 }
 final Map<N, N> parentMap = new HashMap<>();
 parentMap.put(source, null);
 previousReachedNodes = 0;
 reachedNodes = 0;
 for (int depth = 0;; ++depth) {
 final N found = dls(source, 
 depth, 
 parentMap,
 goalNodePredicate);
 if (found != null) {
 return tracebackPath(found, parentMap);
 }
 if (reachedNodes == previousReachedNodes) {
 // We have reached all the nodes of the tree and we did not find
 // any goal node.
 return new ArrayList<>(0);
 }
 previousReachedNodes = reachedNodes;
 reachedNodes = 0;
 }
 }
 private N dls(final N node, 
 final int depth,
 final Map<N, N> parentMap,
 final Predicate<N> goalNodePredicate) {
 ++reachedNodes;
 if (depth == 0) {
 return goalNodePredicate.test(node) ? node : null;
 }
 N found;
 if (node.getLeft() != null) {
 found = dls(node.getLeft(),
 depth - 1, 
 parentMap,
 goalNodePredicate);
 parentMap.put(node.getLeft(), node);
 if (found != null) {
 return found;
 }
 }
 if (node.getRight() != null) {
 found = dls(node.getRight(), 
 depth - 1, 
 parentMap,
 goalNodePredicate);
 parentMap.put(node.getRight(), node);
 if (found != null) {
 return found;
 }
 }
 return null;
 }
}

App.java:

package net.coderodde.graph.tree;
import net.coderodde.graph.tree.support.BreadthFirstSearchNodeFinder;
import net.coderodde.graph.tree.support.DepthFirstSearchNodeFinder;
import java.util.List;
import java.util.Random;
import java.util.function.Predicate;
import net.coderodde.graph.tree.BinaryTree.BinaryTreeNode;
import net.coderodde.graph.tree.support.IDDFSNodeFinder;
public class App {
 /**
 * The minimum key value.
 */
 private static final int MINIMUM = -10000;
 /**
 * The maximum key value.
 */
 private static final int MAXIMUM = 100000;
 /**
 * The size of the tree.
 */
 private static final int SIZE = 1000000;
 /**
 * The entry point into a program.
 * @param args the command line arguments.
 */
 public static void main(final String... args) {
 final long seed = System.currentTimeMillis(); //1431245853421L;
 final Random rnd = new Random(seed);
 final BinaryTree<Integer> tree = createRandomBinaryTree(SIZE,
 MINIMUM,
 MAXIMUM,
 rnd);
 final Integer target = rnd.nextInt(MAXIMUM - MINIMUM + 10) + 
 MINIMUM - 5;
 System.out.println("Seed: " + seed);
 System.out.println("Root: " + tree.getRoot().getElement());
 System.out.println("Target: " + target);
 System.out.println();
 final Predicate<BinaryTreeNode<Integer>> gp = 
 (final BinaryTreeNode<Integer> t) -> t.getElement().equals(target);
 final List<BinaryTreeNode<Integer>> path1 = 
 profileFinder(new DepthFirstSearchNodeFinder<>(), gp, tree.getRoot());
 final List<BinaryTreeNode<Integer>> path2 = 
 profileFinder(new BreadthFirstSearchNodeFinder<>(), gp, tree.getRoot());
 final List<BinaryTreeNode<Integer>> path3 = 
 profileFinder(new IDDFSNodeFinder<>(), gp, tree.getRoot());
 System.out.println("Paths equal: " + listsEqual(path1, path2, path3));
 System.out.println();
 printPath(path1, "DFS path:");
 System.out.println();
 printPath(path2, "BFS path:");
 System.out.println();
 printPath(path3, "IDDFS path:");
 }
 /**
 * Checks that all input lists are of the same length and content.
 * 
 * @param <T> the list component type.
 * @param lists the array of lists.
 * @return <code>true</code> if and only if the lists are same.
 */
 public static <T> boolean listsEqual(final List<T>... lists) {
 if (lists.length < 2) {
 // Trivially equal.
 return true;
 }
 for (int i = 0; i < lists.length - 1; ++i) {
 if (lists[i].size() != lists[i + 1].size()) {
 return false;
 }
 }
 if (lists[0].isEmpty()) {
 // All are empty.
 return true;
 }
 for (int index = 0; index < lists[0].size(); ++index) {
 for (int i = 0; i < lists.length - 1; ++i) {
 for (int j = i + 1; j < lists.length; ++j) {
 if (!lists[i].get(index).equals(lists[j].get(index))) {
 return false;
 }
 }
 }
 }
 return true;
 }
 /**
 * Prints the path.
 * 
 * @param path the path to print.
 * @param title the title message.
 */
 private static void printPath(final List<BinaryTreeNode<Integer>> path,
 final String title) {
 System.out.println(title);
 path.stream().forEach((node) -> {
 System.out.println(node.getElement());
 });
 }
 /**
 * Profiles the input finder, prints its time usage and returns its result
 * path.
 * 
 * @param finder the finder implementation.
 * @param goalPredicate the goal node predicate.
 * @param source the source node.
 * @return a tree path.
 */
 private static List<BinaryTreeNode<Integer>> 
 profileFinder(final AbstractTreeNodeFinder<BinaryTreeNode
 <Integer>> finder,
 final Predicate<BinaryTreeNode<Integer>> goalPredicate,
 final BinaryTreeNode<Integer> source) {
 final long ta = System.currentTimeMillis();
 final List<BinaryTreeNode<Integer>> path = 
 finder.search(source, goalPredicate);
 final long tb = System.currentTimeMillis();
 System.out.println(finder.getClass().getSimpleName() + 
 " in " + (tb - ta) + " ms.");
 return path;
 }
 /**
 * Constructs a binary integer tree with integers within range
 * <tt>[minimum, maximum]</tt>.
 * 
 * @param size the amount of values to create in the tree.
 * @param minimum the minimum value.
 * @param maximum the maximum value.
 * @param rnd the random number generator.
 * @return a random binary tree.
 */
 private static BinaryTree<Integer> 
 createRandomBinaryTree(final int size,
 final int minimum,
 final int maximum,
 final Random rnd) {
 final BinaryTree<Integer> tree = new BinaryTree<>();
 for (int i = 0; i < size; ++i) {
 tree.add(rnd.nextInt(maximum - minimum + 1) + minimum);
 }
 return tree;
 }
}

Any improvements I could do?

Answer 1

On the whole, your code is neat, the style is good, generics look OK. I have a concern with two major 'design' points though.

The first is the AbstractBinaryTreeNode class. This encapsulates the basic functionality of a node in the binary tree, and it makes it seem that there would be a way to customize the implementation.

Unfortunately, you can't.

Your BinaryTree class creates a concrete implementation as a static-internal:

public static final class BinaryTreeNode<E extends Comparable<? super E>> 
 extends AbstractBinaryTreeNode<E, BinaryTreeNode<E>> {

and then only uses this implementation for the root:

/**
 * The root node of this tree.
 */
private BinaryTreeNode<E> root;

Thus the whole thing is moot, and redundant.

The other issue I see is in the AbstractTreeNodeFinder. This has two problems.

The first problem is the concrete method tracebackPath, which has lousy JavaDoc, so I am not sure of its purpose, but the implementation reads like a static method...

I would consider removing that class entirely, and reducing it to a @FunctionalInterface, and then you can pass it in for each search.

There's abstraction overkill in there.