Construct a tree from a given array

Question

I would like to construct a graph from a given array and root where the node is described below,

static class TreeNode {

    private int value;
    private ArrayList<TreeNode> children; 

    public TreeNode(int nodeValue) {
        this.value = nodeValue;
        this.children = new ArrayList<TreeNode>();
    }

    public int getValue() {
        return this.value;
    }

    public void addChild(TreeNode child) {
        this.children.add(child);
    }

    public ArrayList<TreeNode> getChildren() {
        return this.children;
    } 
}

An array provided below to construct the graph,

T[0] = 1
T[1] = 2
T[2] = 3
T[3] = 3
T[4] = 2
T[5] = 1
T[6] = 4

Array T describes a network of cities if T[P] = Q and P ≠ Q, then there is a direct road between cities P and Q. If the index of 2 is root, then the graph is provided below,

Obviously, I can do it manually for the given array,

    final int N = 7;
    TreeNode[] nodes = new TreeNode[N];

    for (int i = 0; i < N; i++) {
        nodes[i] = new TreeNode(i);
    }


    TreeNode root = nodes[2];

    root.addChild(nodes[1]);
    root.addChild(nodes[3]);
    root.addChild(nodes[4]);


    nodes[1].addChild(nodes[0]);
    nodes[1].addChild(nodes[5]);

    nodes[4].addChild(nodes[6]);

How do I construct programmatically when I have given an array and K value? Please help.

@nicomp I'm still trying to write it properly. I will update here when I'm done — Arefe
– Arefe, Commented Jul 13, 2018 at 9:59

Mike Housky · Accepted Answer · 2018-07-13 09:59:18Z

2

After you construct the TreeNode[] array, it's easy:

TreeNode root = null;
for (int i=0; i<T.length; ++i) {
    if (T[i] == i) { // if it's a root node
        //TODO: Test for multiple root nodes here
        root = nodes[i];
    } else {
        nodes[T[i]].addChild(nodes[i]);
    }
}

I would add a private TreeNode parent; object to the TreeNode class, initialize it to null and set it to the parent reference in the addChild method. That's handy to have during debug, even if you don't need it for the first use of this class. Maybe you'll need it later.

answered Jul 13, 2018 at 9:59

Mike Housky

4,0891 gold badge20 silver badges31 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Arefe Over a year ago

I would like to accept your answer, but the output is not completely correct. I run the code and get:

The root = 3 Parent 3 has children = 2 Parent 2 has children = 1 Parent 2 has children = 4 Parent 1 has children = 0 Parent 1 has children = 5 Parent 4 has children = 6

The root is 2 and the Parent 3 has children = 2 is not correct and actually opposite is true

Tomek Szpakowicz Over a year ago

@Arefe This does not really follow from the data that you provided. T[2] = 3 says that 3 is a parent of 2, so 2 cannot be a root. And T[3] = 3 shows that 3 has no parent, so it is a root. Are there some additional rules and parameters that make 2 a root? If so, what if 3 was really a part of a tree, eg. T[3] = 7; T[7] = 8; T[8] = 8; T[9] = 8; T[10] = 9; and so on...?

Arefe Over a year ago

Yes, the root index K is given where you will need to start. So, even if T[children] = parent, if T[K] = V then the K is the parent of V. How do I change the code now

Liad Saubron · Accepted Answer · 2018-07-13 09:58:24Z

1

Iterate over all nodes, for each node get the node's value and add the current node to the node at the value.

for (int i = 0; i < N; i++) {
    nodes[nodes[i].getValue()].addChild(nodes[i])
}

answered Jul 13, 2018 at 9:58

Liad Saubron

794 bronze badges

Comments

Arefe · Accepted Answer · 2018-07-13 11:42:45Z

I write an answer, however, it's not showing all the children. The code is provided below,

public class App {

    static class TreeNode {

        private int value;
        private ArrayList<TreeNode> children;

        public TreeNode(int nodeValue) {
            this.value = nodeValue;
            this.children = new ArrayList<TreeNode>();
        }

        public int getValue() {
            return this.value;
        }

        public void addChild(TreeNode child) {
            this.children.add(child);
        }

        public ArrayList<TreeNode> getChildren() {
            return this.children;
        }
    }


    public static TreeNode buildGraph(int[] T, int K) {

        final int N = T.length;

        TreeNode[] nodes = new TreeNode[N];

        for (int i = 0; i < N; i++) {
            nodes[i] = new TreeNode(i);
        }

        /*
            T[0] = 1
            T[1] = 2
            T[2] = 3
            T[3] = 3
            T[4] = 2
            T[5] = 1
            T[6] = 4

                 2 - 3
                / \
               1   4
              / |  |
             0  5  6
        * */

        TreeNode root = nodes[K];

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        boolean[] visited = new boolean[N];

        while (!queue.isEmpty()) {

            TreeNode node = queue.poll();
            int index = node.getValue();

            visited[index] = true;

            // T[3] = 3 is a leaf with no further connection to develop
            if (index == T[index]) {
                continue;
            }

            // 2 != 3 for the root node and we havent visited node 3 earlier
            if (index != T[index] && !visited[T[index]]) {

                node.addChild(nodes[T[index]]);
                queue.offer(nodes[T[index]]);
            }

            int left = 0, right = N - 1;

            while (left < index && right > index) {

                if (T[left] == index) {

                    node.addChild(nodes[left]);
                    queue.offer(nodes[left]);
                }

                if (T[right] == index) {

                    node.addChild(nodes[right]);
                    queue.offer(nodes[right]);
                }

                left++;
                right--;
            }
        }

        return root;
    }

    public static void main(String[] args) {

        int[] T = new int[7];

        T[0] = 1;
        T[1] = 2;
        T[2] = 3;
        T[3] = 3;
        T[4] = 2;
        T[5] = 1;
        T[6] = 4;

        TreeNode root = buildGraph(T, 2);

        System.out.println("The root = " + root.getValue());

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){

            TreeNode node = queue.poll();

            ArrayList<TreeNode> children = node.getChildren();

            for (int i = 0; i < children.size(); i++) {

                TreeNode child = children.get(i);
                queue.offer(child);

                System.out.println("Parent "+ node.getValue()+ " has children = "+ child.getValue());
            }
        }
    }
}

At the time I run, I get output like,

The root = 2
Parent 2 has children = 3
Parent 2 has children = 1
Parent 1 has children = 0

Anyone can help me to correct how do I miss the other children?

Update

I write it based on the other answer which seems simpler.

public static TreeNode buildGraph1(int[] T, int K) {

        final int N = T.length;

        TreeNode[] nodes = new TreeNode[N];

        for (int i = 0; i < N; i++) {
            nodes[i] = new TreeNode(i);
        }

        /*
       T[children] = parent if the children != K

            T[0] = 1
            T[1] = 2
            T[2] = 3
            T[3] = 3
            T[4] = 2
            T[5] = 1
            T[6] = 4

                 2 - 3
                / \
               1   4
              / |  |
             0  5  6
        * */

        TreeNode root = nodes[K];
        int value = root.getValue();

        if (T[K] != K) {
            nodes[K].addChild(nodes[T[K]]);
        }

        for (int i = 0; i < T.length; ++i) {

            if (K == i) {
                continue;
            }

            if (T[i] != i) {
                nodes[T[i]].addChild(nodes[i]);
            }
        }

        return root;
    }

The output is provided below:

The root = 2
Parent 2 has children = 3
Parent 2 has children = 1
Parent 2 has children = 4




Parent 1 has children = 0
Parent 1 has children = 5


Parent 4 has children = 6

Collectives™ on Stack Overflow

Construct a tree from a given array

3 Answers 3

3 Comments

Comments

Update

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

Update

Comments

Your Answer

Sign up or log in

Post as a guest

Related