How to implement a binary tree Using HashMap Collection in java

[madhu.garimilla]

Hi,

If any one knows how to implement a binary tree using hashmap collection in java please reply. Thanks a lot in advance

[TheGathering]

Can you provide more specifics? Such as:
Does the tree have to be balanced? Are you populating the tree based on the keys or values? Is the tree an object tree or an array representation of a tree?

I can't think of any practical applications of making a binary tree from a HashMap as you're going from an O(1) data structure to an O(log n) data structure, but if you really want to make one:

1.) Use java's default packages:

HashMap orginal = new HashMap();
original.put("hi", "hello");
...

TreeSet toUse = new TreeSet();
toUse.addAll(original.keySet());
/* (or original.values() depending on
what you're populating to the treemap*/

A treeset is a tree representation of a set collection, which meets your requirements for a binary tree. You can then use the values in the treeset as keys to reference data in HashMap, or just hold the values in treeset and not use the HashMap at all.

2.) Create your own:

Create a treenode class that holds two other treenode objects, one for the left branch one for a right branch. Also add a value and key object to the treenode class to store the value and keys from the hashmap.

Then you simply call:
HashMap orginal = new HashMap();
original.put("hi", "hello");
...

Iterator iter = original.keySet().iterator();

Once you have an iterator you can use .next() to move through the HashMap, get values, and add them to the tree by iterating through the tree until you find a suitable place to put the value. How you implement the add is dependent on the requirements of the tree.

Note: This code is not compiled so there might be errors, but the errors should be minor and easy to fix.

Hope that helps :)