Retrieve all the leaf nodes of java TreeMap

Question

Is there a way to retrieve all the leaf nodes of a Java TreeMap?

I have a TreeMap like this

TreeMap<String, FooBar> myTree = new TreeMap<String, FooBar>(new Comparator<String>() {
  public int compare(String o1, String o2)
  {
    int b1 = Integer.parseInt(o1, 2);
    int b2 = Integer.parseInt(o2, 2);
    return (b1 > b2 ? 1 : (b1 == b2 ? 0 : -2));
  }
});

How do I get all the leaf nodes of this tree?

This doesn't make sense. The elements stored at the leaves are dependent on how the implementation of `TreeMap` balances the tree. Are you trying to benchmark the performance of the implementation? — Andrew Mao, Mar 22 '13 at 05:26
I know how to do that. In TreeMap all leaves are null. So you have them. Bottommost Entry is not a leaf. I think so. — Volodymyr Levytskyi, Aug 10 '13 at 14:40

score 2 · Accepted Answer · edited Oct 21 '13 at 17:38

This doesn't make much sense to me. The elements stored at the leaves are dependent on how the implementation of TreeMap balances the tree.

But, let's say you needed to do this for some reason. To actually do this, you would need to do a bit of a hack: write a class packaged in java.util that can access the package private methods of TreeMap.

After doing some more digging, I found that the default tree implementation in the JDK is a red-black tree, and its Entry implementation look like the following:

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left = null;
    Entry<K,V> right = null;
    Entry<K,V> parent;
    boolean color = BLACK;

    ....

There doesn't seem to be any direct way to get at the root. But, if you can grab one of these Entryies, though, you can traverse the parent all the way up to the root, then do a traversal of the tree any way you want to get the leaves (Entry where left == null and right == null). An inorder traversal would preserve the sorted ordering.

But, to reiterate, I don't see any good reason why you'd want to do this. You'd also need to do it in the java.util package to be able to investigate those Entryies. But here's code, for fun. (You won't be able to execute this without overriding the security restrictions on the JVM.)

package java.util;

import java.util.TreeMap.Entry;

public class TreeMapHax {

    static <K,V> List<Entry<K, V>> getLeafEntries(TreeMap<K, V> map) {      
        Entry<K, V> root = map.getFirstEntry();
        while( root.parent != null ) root = root.parent;

        List<Entry<K,V>> l = new LinkedList<Entry<K,V>>();
        visitInOrderLeaves(root, l);
        return l;
    }

    static <K,V> void visitInOrderLeaves(Entry<K, V> node, List<Entry<K, V>> accum) {       
        if( node.left != null ) visitInOrderLeaves(node.left, accum);       
        if( node.left == null && node.right == null ) accum.add(node);      
        if( node.right != null ) visitInOrderLeaves(node.right, accum);
    }

    public static void main(String[] args) {
        TreeMap<String, Integer> map = new TreeMap<String, Integer>();

        for( int i = 0; i < 10; i++ )
            map.put(Integer.toString(i), i);

        System.out.println(getLeafEntries(map));
    }

}

This seems to be the only way other than implementing my own tree structure. The only problem I have with this approach is that it wouldn't work on another machine, would it? But in any case, this will do for now. — 0x56794E, Mar 22 '13 at 05:58
Can you explain why you would even want to do this other than just for hacking purposes? — Andrew Mao, Mar 22 '13 at 06:07
i'm working on the region-partition piece of a project. Each node of the tree represents a region and, if gets partition, would have two children. Let's say I have region R0 gets divided into R1 and R2 (there're other algorithm specified in the comparator to determine which one would be the left and which one would be the right node). Assume R1 is left for now. Then if R1 gets divided again, it would have 2 children, say R3 and R4. At the end, I want to get all the sub regions (the leaves) in a particular order. — 0x56794E, Mar 22 '13 at 06:14
You understand that the tree rotates to balance itself, right? Even if you can interpret the tree as you say, the parent-child relationships can switch. The comparator you specify only determines the in-order traversal relationships and cannot enforce parent-child relationships. — Andrew Mao, Mar 22 '13 at 06:35
Good point. Do you have any suggestions on which data structure would be best for enforcing this kind of parent-child relationship? — 0x56794E, Mar 22 '13 at 06:50
However, I'm almost positive that the tree I'm building would always be a balanced tree since I'm using spectral partitioning algorithm. The next node gets partitioned is always the "largest" leaf. — 0x56794E, Mar 22 '13 at 06:52
I see what you're saying, but I don't agree that it will work that way. It sounds like you are trying to build a red-black tree without causing any rebalancing to happen. This is bug-prone because the `TreeMap` might still rotate when you don't expect it to. It will be good if you post a new question describing what you are trying to do. — Andrew Mao, Mar 22 '13 at 17:06

Retrieve all the leaf nodes of java TreeMap

1 Answers1

Linked