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;
}
}

Answer 2

Your tree looks weird - both child of parent node 11 is 10. What is the point? Should not they be merged into one? Anyway please check parallel tree elated threads. Java tree data-structure?

It should help.

In general you need to create Node class that contains idx\value of exact node and links to two child nodes. Recursively you'll be able to build such data structure.