AbstractBinarySearchTree extends AbstractSearchTree<E, N> { @Override public N predecessor(N node) { if (node.getLeftChild() != null) { return maximum((N) node.getLeftChild()); } BinaryTreeNode<E> current = node; BinaryTreeNode<E> parent = current.getParent(); while (parent != null && current == parent.getLeftChild()) { current = parent; parent = parent.getParent(); } return (N) parent; } protected  AbstractBinarySearchTree(Comparator<E> comparator, TreeNodeFactory<E, N> factory); @Override N find(E value); @Override N find(N root, E value); @Override N minimum(); @Override N minimum(N root); @Override N maximum(); @Override N maximum(N root); @Override N predecessor(N node); @Override N successor(N node); @Override N insert(E value); @Override List<N> delete(E... values); @Override N delete(E value);  }
@Test public void testFindingThePredecessorOnFullTree() throws Exception { final BinaryTreeNode<Integer> one = create(1); final BinaryTreeNode<Integer> two = create(5); final AbstractBinarySearchTree<Integer, BinaryTreeNode<Integer>> tree = tree(create(6, create(3, one, two), create(9, create(7), create(11, create(10), create(12))))); assertThat(tree.predecessor(tree.getRoot()), is(notNullValue())); assertThat(tree.predecessor(tree.getRoot()).getValue(), is(5)); assertThat(tree.predecessor(one), is(nullValue())); assertThat(tree.predecessor(two), is(notNullValue())); assertThat(tree.predecessor(two).getValue(), is(3)); }