Create a Binary Tree from an Array

Question

I need to create a tree from an array after processing the elements by following algorithm:

1. let A[n] be the array
2. while lenght(A) > 1
3.      for i = 0 to lenght(A)-2
4.          new_A[i] = max(A[i], A[i+1]) + 1
5.      end for
6.      [minValue, minIndex] = someFunction(new_A) // someFunction returns the minimum value and index of the same
7.      delete A[minIndex] and A[minIndex + 1] from A and insert minValue in that place // basically A[minIndex] and A[minIndex + 1] are being replaced by minValue
8.  // This is how the length of A is being decreased by 1 in each iteration    
9. end while

Example:

+--------------+----------------------+-----------------+---------------+
| iteration No | Array A              | Array new_A     | Remarks       |
+--------------+----------------------+-----------------+---------------+
|            1 | 5-9-3-2-1-6-8-3      |10-10-4-3-7-9-9  | minValue = 3  |
|              |                      |                 | minIndex = 3  |
+--------------+----------------------+-----------------+---------------+ 
|            2 | 5-9-3-3-6-8-3        |10-10-4-7-9-9    | minValue = 4  |
|              |                      |                 | minIndex = 2  |
+--------------+----------------------+-----------------+---------------+ 
|            3 | 5-9-4-6-8-3          |10-10-7-9-9      | minValue = 7  |
|              |                      |                 | minIndex = 2  |
+--------------+----------------------+-----------------+---------------+ 
|            4 | 5-9-7-8-3            |10-10-9-9        | minValue = 9  |
|              |                      |                 | minIndex = 2  |   
+--------------+----------------------+-----------------+---------------+ 
|            5 | 5-9-9-3              |10-10-10         | minValue = 10 |
|              |                      |                 | minIndex = 0  |
+--------------+----------------------+-----------------+---------------+ 
|            6 | 10-9-3               |11-10            | minValue = 10 |
|              |                      |                 | minIndex = 1  |
+--------------+----------------------+-----------------+---------------+ 
|            7 | 10-10                |11               | minValue = 11 |
|              |                      |                 | minIndex = 0  |
+--------------+----------------------+-----------------+---------------+ 
|            8 | 11                   |--               | --            |
+--------------+----------------------+-----------------+---------------+

Until this everything is okay. But I need to represent this in a tree. The resulting tree will be as follows:

 iteration# 8           11
                       /  \
                      /    \  
 iteration# 7        /      \------- 10          
                    /               /  \
 iteration# 6     10               /    \  
                 /  \             /      \ 
 iteration# 5   |    |           9        \
                |    |          / \        \
 iteration# 4   |    |         7   \        \
                |    |        / \   \        |
 iteration# 3   |    |       4   \   \       |
                |    |      / \   \   \      |
 iteration# 2   |    |     /   3   \   \     |
                |    |    /   / \   \   \    |
 iteration# 1   5    9   3   2   1   6   8   3

The logic is to get the minValue and make it a root and make the corresponding array elements (from which the minValue came) children. This is how we can grow the tree. It can be somehow called a binary tree as each node has exactly 2 children. The problem I am facing is that if I take previous root as one of the children I might not get the exact answer. Because see in the iteration 5, the minValue I am getting is not the contribution of previous root. So now my whole previously made tree might get lost. Is there anything I can do to get the whole tree structure? I am using JAVA.

EDIT: Is there any way to create a tree from the bottom (i.e. the leaf node) in JAVA. Like first create a parent with two children, then put this parent as a child of another node and gradually reach to the top. So taking into account above example can anyone help me write the code. Below is my code, I am just not able to create the tree from the leaf.

public class Main {

private static int GATE_COST = 1;
private static BinaryTree bt;
private static float num;

public static void main(String[] args) throws IOException {
    File filePin = new File("C:/somePath/files/pin.txt");
    BufferedReader buffer = new BufferedReader(new FileReader(filePin));
    String line = buffer.readLine();
    int lenData = Integer.parseInt(line.trim());
    float[] data = new float[lenData];
    for (int i = 0; i < lenData; i++) {
        line = buffer.readLine();
        data[i] = Float.parseFloat(line.trim());
    }
    bt = new BinaryTree();
    num = sysnthesis(data);
    System.out.println("\nArrival: " + num);
}

private static float sysnthesis(float[] data) {
    while (data.length > 1) {
        for (int i = 0; i < data.length; i++) { 
            System.out.print(data[i] + " ");
        }
        float[] cost = getCost(data);

        float minValue = cost[0];
        int minIndex = 0;
        for (int i = 0; i < cost.length; i++) {
            if (cost[i] < minValue) {
                minValue = cost[i];
                minIndex = i;
            }
        }
        createTree(data, minValue, minIndex); // I am not able to create its body
        data = getNewData(data, minValue, minIndex);
        System.out.print("\n");
    }
    System.out.print(data[0]);
    return data[0];
}

private static float[] getCost(float[] data) {
    float[] cost = new float[data.length - 1];
    for (int i = 0; i < data.length - 1; i++) {
        cost[i] = Math.max(data[i], data[i+1]) + GATE_COST; 
    }
    return cost;
}

private static float[] getNewData(float[] data, float minValue, int minIndex) {
    float[] newData = new float[data.length - 1];
    int i = 0;
    for (; i < minIndex; i++) {
        newData[i] = data[i];
    }
    newData[i++] = minValue;
    for (; i < data.length - 1; i++) {
        newData[i] = data[i+1];
    }
    return newData;
}


private static void createTree(float[] data, float minValue, int minIndex) {
    /**
    My code goes here
  */
}
}

pin.txt contains something like this:

8
5.0
9.0
3.0
2.0
1.0
6.0
8.0
3.0

Thanks in advance

Answer 1

I think I did find the answer to my problem myself, so just wanna share it. Its kind of complex solution, but it works perfectly and I tried with 10-100 input pins, it gives me correct tree. I am sharing the JAVA code.

Main.java

public class Main {

private static int GATE_COST = 1;
private static BinaryTree bt;
private static ArrayList<Node> arrNodes;
private static int currDepth = 0;

public static void main(String[] args) throws IOException {
    File filePin = new File("C:/Users/Arindam/workspace/TreeSynthesis/files/pin.txt");
    BufferedReader buffer = new BufferedReader(new FileReader(filePin));
    String line = buffer.readLine();
    int lenData = Integer.parseInt(line.trim());
    float[] data = new float[lenData];
    for (int i = 0; i < lenData; i++) {
        line = buffer.readLine();
        data[i] = Float.parseFloat(line.trim());
    }
    arrNodes = new ArrayList<Node>();
    bt = new BinaryTree();
    String arrival = sysnthesis(data);
    System.out.println("Arrival: " + arrival);
    System.out.println("Topology: ");
    bt.printPostorder();
}

private static String sysnthesis(float[] data) {
    ArrayList<Node> dataNodes = convertArraytoNode(data);
    while (dataNodes.size() > 1) {
        for (int i = 0; i < dataNodes.size(); i++) { 
            System.out.print(dataNodes.get(i).getData() + " ");
        }
        float[] cost = getCost(dataNodes);

        float minValue = cost[0];
        int minIndex = 0;
        for (int i = 0; i < cost.length; i++) {
            if (cost[i] < minValue) {
                minValue = cost[i];
                minIndex = i;
            }
        }
        createTree(dataNodes, minValue, minIndex);
        dataNodes = getNewDataNodes(dataNodes, minValue, minIndex);
        //bt.printPostorder();
        System.out.println();
    }
    System.out.print(dataNodes.get(0).getData()+ "\n");
    return dataNodes.get(0).getData();
}

private static ArrayList<Node> convertArraytoNode(float[] data) {
    ArrayList<Node> dataNodes = new ArrayList<Node>();
    for (int i = 0; i < data.length; i++) {
        dataNodes.add(new Node(Float.toString(data[i]), 0));
    }
    return dataNodes;
}

private static float[] getCost(ArrayList<Node> dataNodes) {
    float[] cost = new float[dataNodes.size() - 1];
    for (int i = 0; i < dataNodes.size() - 1; i++) {
        cost[i] = Math.max(Float.parseFloat(dataNodes.get(i).getData()), 
                Float.parseFloat(dataNodes.get(i+1).getData())) + GATE_COST; 
    }
    return cost;
}

private static ArrayList<Node> getNewDataNodes(ArrayList<Node> dataNodes, float minValue, int minIndex) {
    dataNodes.get(minIndex).setData(Float.toString(minValue));
    dataNodes.get(minIndex).setDepth(currDepth);
    dataNodes.remove(minIndex + 1);
    return dataNodes; 
}


private static void createTree(ArrayList<Node> dataNodes, float minValue, int minIndex) {
    Node root = null, lChild = null, rChild = null;
    root = new Node(Float.toString(minValue), ++currDepth);
    int flag = 0;
    ArrayList<Integer> deleteIndex = new ArrayList<Integer>();
    if (!arrNodes.isEmpty()) {
        for (int i = 0; i < arrNodes.size(); i++) {
            if (arrNodes.get(i).getData().equals(dataNodes.get(minIndex).getData()) &&
                    dataNodes.get(minIndex).getDepth() == currDepth - arrNodes.size() + i) {
                flag++;
                lChild = arrNodes.get(i);
                deleteIndex.add(i);
            }
            else if (arrNodes.get(i).getData().equals(dataNodes.get(minIndex + 1).getData()) &&
                    dataNodes.get(minIndex + 1).getDepth() == currDepth - arrNodes.size() + i) {
                flag++;
                rChild = arrNodes.get(i);
                deleteIndex.add(i);
            }
        }
        if (flag == 0) {
            lChild = new Node(dataNodes.get(minIndex).getData(), 0);
            rChild = new Node(dataNodes.get(minIndex + 1).getData(), 0);
        } else if (flag == 1 && null ==  rChild){
            rChild = new Node(dataNodes.get(minIndex + 1).getData(), 0);
        } else if (flag == 1 && null ==  lChild) {
            lChild = new Node(dataNodes.get(minIndex).getData(), 0);
        }
        for (int i = deleteIndex.size() - 1; i > 0; i--) {
            dataNodes.remove(deleteIndex.get(i));
        }
    } else {
        lChild = new Node(dataNodes.get(minIndex).getData(), 0);
        rChild = new Node(dataNodes.get(minIndex + 1).getData(), 0);
    }
    bt.buildTree(root, lChild, rChild);
    arrNodes.add(bt.getRootNode());
}
}

BinaryTree.java

public class BinaryTree { 

private Node root; 

public BinaryTree() { 
    root = null; 
} 


public void buildTree(Node rt, Node lChild, Node rChild) { 
  root = rt; 
  root.left  = lChild; 
  root.right = rChild;
}

public int size() { 
    return(size(root)); 
}
private int size(Node node) { 
    if (node == null) return(0); 
    else { 
        return(size(node.left) + 1 + size(node.right)); 
    } 
}

public int maxDepth() { 
    return(maxDepth(root)); 
}
private int maxDepth(Node node) { 
    if (node==null) { 
        return(0); 
    } 
    else { 
        int lDepth = maxDepth(node.left); 
        int rDepth = maxDepth(node.right);

        // use the larger + 1 
        return(Math.max(lDepth, rDepth) + 1); 
    } 
}

public void printTree() { 
    printTree(root); 
    System.out.println(); 
}
private void printTree(Node node) { 
    if (node == null) return;
    printTree(node.left); 
    System.out.print(node.data + "  "); 
    printTree(node.right); 
}

public void printPostorder() { 
    printPostorder(root); 
    System.out.println(); 
}

public void printPostorder(Node node) { 
    if (node == null) return;

    printPostorder(node.left); 
    printPostorder(node.right);

    System.out.print(node.data + "  "); 
}

public Node getRootNode() {
    return root;
}

public int getNodeDepth() {
    return root.depth;
}

public Node getRChildNode() {
    return root.right;
}

public Node getLChildNode() {
    return root.left;
}
}

Node.java

public class Node {
Node left; 
Node right; 
String data;
int depth;

Node(String newData, int depth) { 
    this.left = null; 
    this.right = null; 
    this.data = newData;
    this.depth = depth;
}

public Node getLeft() {
    return left;
}

public void setLeft(Node left) {
    this.left = left;
}

public Node getRight() {
    return right;
}

public void setRight(Node right) {
    this.right = right;
}

public String getData() {
    return data;
}

public void setData(String data) {
    this.data = data;
}

public int getDepth() {
    return depth;
}

public void setDepth(int depth) {
    this.depth = depth;
}
}