Java Binary Search Tree - Compute the length of a path to a node

Question

Using Java's TreeMap implementation, how is it possible to compute the length of a path to a specified node within the tree? By this I mean to count the number of comparisons carried out whilst searching the node in the Binary Search Tree.

Answer 1

TreeMap has a constructor that takes a Comparator as an argument. The comparator is used to order keys stored in the map. If you literally want to "count the number of comparisons carried out", you could write an instrumented comparator that counts the number of times it's called.

public class StringComparator implements Comparator<String> {
    private int count = 0;

    @Override
    public int compare(String o1, String o2) {
        ++count;
        return o1.compareTo(o2);
    }

    public int getCount() { return count; }
    public void reset() { count = 0; }

    public static void main(String[] args) {
        StringComparator sc = new StringComparator();
        TreeMap<String, String> map = new TreeMap<>(sc);
        map.put("foo", "one");
        System.out.println("foo took " + sc.getCount() + " comparisons");
        sc.reset();
        map.put("bar", "two");
        System.out.println("bar took " + sc.getCount() + " comparisons");
    }
}