Note :- Using java 8 and above.
Hi there…
Today, I am going to write a java program which will take an var-arg of character, you can use any data-type you want. Data type is not the focus here.
The main focus is the process of creating a binary tree.
I am using functional programming to do object creation. Because, I think it makes me look cool. 🙂
For that Purpose, I am using java.util.function.Function, it is a Functional Interface. I provide a char-value and it returns me an instance of BinaryTreeNode.
//Using BinaryTreeNode constructor which takes a charachter and created a private static final Function<Character, BinaryTreeNode> charToTreeNode = BinaryTreeNode::new;
And how it’s used in the function to create an object.
indexToNodeMap.put(i, charToTreeNode.apply(names[i]) );
In the above code, the charToTreeNode.apply(names[i]) is where we are calling the lambda, and we pass a charchter in it, to get a instance of BinaryTreeNode.
Ok. so far all is good.
Coming to algorithm for creating a tree from the data – is very simple.
- loop on the sequence of data
- create a BinaryTreeNode object
- put the index and node object in a map – as key-value pair
- init a variable parent to -1 and loop until parent is less than the length of the array
- increment the parent counter to make it point to the next unprocessed location
- calculate the index of left child = (2 * parent) + 1
- if the left child is present in the map
- then set the left node to point to the node present at key in the map that we created above.
- calculate the index of right child, right = (left + 1)
- if the index of right-child is in the limits of array length
- then set the right-node to point to the node present in the map at key right-child-index.
- if the index of right-child is in the limits of array length
- return the node mapped to key 0 in the map. Because, the index 0 is the root of this tree.
Complete Code :-
import java.util.Map; import java.util.HashMap; import java.util.function.Function; public class CreateBinaryTree { //Using BinaryTreeNode constructor which takes a charachter and created a BinaryTreeNode private static final Function<Character, BinaryTreeNode> charToTreeNode = BinaryTreeNode::new; public static BinaryTreeNode createCompleteBinaryTree(char ... names) { //Create Nodes and Put it in a map Map<Integer, BinaryTreeNode> indexToNodeMap = new HashMap<>(); for(int i=0; i<names.length; ++i) { indexToNodeMap.put(i, charToTreeNode.apply(names[i])); } //Now run over the array and connect the nodes int p = -1; int l = -1; int r = -1; while( ++p < names.length) { if( (l = (2 * p) + 1) < names.length ) { //Attach Left child indexToNodeMap.get(p).left = indexToNodeMap.get(l); if( (r = l + 1) < names.length ) { //Attach right child indexToNodeMap.get(p).right = indexToNodeMap.get(r); } } } return indexToNodeMap.get(0); } }