Height of a TreeSet in Java?

Question

Is that possible to compute the exact height of the Red-Black tree used in the TreeSet class in Java? I don't care about time complexity at all.

Moreover, is it possible to know how many children (0 or 2) a node has in the TreeSet object.

Note that we don't have access to anything but a reference to an object of TreeSet.

Answer 1

Given only a reference, there is nothing you can do without reflection. With reflection on a TreeSet instance T, you will want to:

1. access its backing NavigableMap, which by default will be a TreeMap. Let us call it M.
2. access M's root, of type TreeMap.Entry
3. use a simple recursive algorithm to get depth (max depth = height) and any other information on the nodes.

This may seem daunting, but it is actually much easier than it appears:

public class TreeSpy {

    private static Object get(Object o, String fieldName) {
        try {
            Field declaredField = o.getClass().getDeclaredField(fieldName);
            declaredField.setAccessible(true);
            return declaredField.get(o);
        } catch (Exception e) {
            System.err.println("Could not gain access to field "
                    + fieldName + " of " + o.getClass());
            e.printStackTrace();
            return null;
        }
    }

    private static int diveInto(Object n, int depth, String indent) {
        if (n == null) return depth-1; // we are empty, and should not be counted
        Object left = get(n, "left");
        Object right = get(n, "right");
        String key = (String)get(n, "key");

        int childrenCount = 0 + (left!=null?1:0) + (right!=null?1:0);
        System.out.println(indent + key +
                ": depth=" + depth + ", chidren=" + childrenCount);
        return Math.max(
                diveInto(left,  depth+1, indent+"  "),
                diveInto(right, depth+1, indent+"  "));
    }

    public static void showDepthAndChildren(TreeSet<String> set) {
        TreeMap<String, Object> m = (TreeMap<String, Object>)get(set, "m");
        Object root = get(m, "root");
        int maxDepth = diveInto(root, 1, "");
        System.out.println("Height = Max Depth = " + maxDepth);
    }

    public static void main(String ... args) {
        TreeSet<String> test = new TreeSet<>();
        for (String s : "once upon a time in a galaxy far far away".split(" ")) {
            test.add(s);
        }
        showDepthAndChildren(test);
    }
}

Note that we cannot mention the type of nodes explicitly, because the class TreeMap.Entry has private access. However, we can still use objects of the type to inspect properties.

The output on my machine (JDK8) is:

once: depth=1, chidren=2
  galaxy: depth=2, chidren=2
    away: depth=3, chidren=2
      a: depth=4, chidren=0
      far: depth=4, chidren=0
    in: depth=3, chidren=0
  upon: depth=2, chidren=1
    time: depth=3, chidren=0
Height = Max Depth = 5