Create a complete binary tree from an array of data in java

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.

1. loop on the sequence of data
   1. create a BinaryTreeNode object
   2. put the index  and node object in a map – as key-value pair
2. init a variable parent to -1  and loop until parent is less than the length of the array
   1. increment the parent counter to make it point to the next unprocessed location
   2. calculate the index of left child = (2 * parent) + 1
   3. if the left child is present in the map
      1. then set the left node to point to the node present at key in the map that we created above.
      2. calculate the index of right child, right = (left + 1)
         1. if the index of right-child is in the limits of array length
            1. then set the right-node to point to the node present in the map at key right-child-index.
3. 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);
    }

}