CODEWITHSUNDEEP
javascriptarraystreetransformtree-structure
Paul M.
Paul M.

Reputation: 108

how to transform an Array to an N-ary tree?

I have an Array that I need to transform it to an N-ary tree. I know the value of N, and the total number of nodes.

I give you an example in the picture below. The N-ary tree should be ordered as illustrated.

Link to image here

I can't figure it out. I need an algorithm to do that. The program I'm writing is in javascript but an answer in pseudocode is fine also.

Appreciate your help!

[Edited]

I found a solution using the algorithm from here: Construct a complete K-ary tree from preorder traversal

Upvotes: 2

Views: 3768

Answers (2)

Paul M.
Paul M.

Reputation: 108

I found a solution using the algorithm from here:

Construct a complete K-ary tree from preorder traversal

Upvotes: 2

bytefire
bytefire

Reputation: 4422

Here is a pseudo code/ C# version. Please ask any C# related questions in comments. The key thing here is use of a first-in-first-out data structure, the queue parents in the snippet below. The method convertToN_aryTree returns root node of the resulting n-ary tree.

public class Node
{
    public int data;
    public int nCount; // 'n' in n-ary
    public Node[] children; // this needs to be initialised to length n

    public Node(int d, int n)
    {
        data = d;
        nCount = n;
        children = new Node[n];
    }
}

// data is teh array and n is branch factor of the tree
Node convertToN_aryTree(int[] data, int n)
{
    if(data.Length == 0)
    {
        return null;
    }
    Node root = new Node(data[0], n);
    Node currParent = root;
    Node curr;
    int currChildCount = 0;
    Queue<Node> parents = new Queue();
    for(int i = 1; i<data.Length; i++)
    {
        curr = new Node(data[i], n);
        currParent.children[currChildCount] = curr;
        parents.Enqueue(curr);

        currChildCount++;
        if(currChildCount >= n) // finished with children of this node, so start adding to children of the next.
        {                       // next node is either a sibling or a child but that is taken care of by Queue.
            currParent = parents.Dequeue();
            currChildCount = 0;
        }
    }

    return root;
}

Upvotes: 0

Related Questions