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

Q: Is there anything I can do to get the whole tree structure? A: Whenever you create a tree like this, you'll almost always save the initial node in a separate variable, e.g. "root". EXAMPLE: `Node root = null;`. — paulsm4, Oct 30 '15 at 00:21
@paulsm4: You mean create an ArrayList or something of type Node and save the previous node in the ArrayList whenever I make new tree? — OptimusPrime, Oct 30 '15 at 00:33
No. I mean a "tree" consists of "nodes". Each node contains 1) data, and 2) links to adjoining nodes. The "adjoining nodes" will change as you build your tree. But you always want to save a reference to the first, "root" node. — paulsm4, Oct 30 '15 at 01:17
(The "logic" (of `someFunction`) would seem to be _take two adjacent nodes with minimal maximum, create as a new parent for these a node with the successor of that maximum_) — greybeard, Oct 30 '15 at 05:14
@paulsm4: I am able to create node and linking two child nodes and all. But the real problem is if you look closely in the iteration 5. until iteration 4 the previous node was one of the children of new parent node. But in iteration 5, minValue is something else and finally in iteration 6 these two values are the children of new parent node. My problem is I have to store the entire tree in some temporary variable. But beforehand I don't know how many such temp variable I need. So I was looking for some workaround to make this tree. — OptimusPrime, Oct 30 '15 at 05:59

score 1 · Accepted Answer · answered Oct 31 '15 at 08:11

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

score 0 · Answer 2 · edited May 23 '17 at 12:24

0

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.

edited May 23 '17 at 12:24

Community

1
1

answered Oct 30 '15 at 00:39

vvg

6,325
19
36

It does not matter what the values are. The can be equal. Its not a BST. – OptimusPrime Oct 30 '15 at 01:15
I am able to create node and linking two child nodes and all. But the real problem is if you look in the iteration 5. until iteration 4 the previous node was one of the children of new parent node. But in iteration 5, minValue is something else and finally in iteration 6 these two values are the children of new parent node. My problem is I have to store the entire tree in some temporary variable. But beforehand I don't know how many such temp variable I need. So I was looking for some workaround to make this tree. – OptimusPrime Oct 30 '15 at 05:57

Create a Binary Tree from an Array

2 Answers2