Convert Multidimensional Tree into Array

• Download source code - 25.9 KB

Introduction

There are some easy ways to convert a binary tree to an array. But the complexity increases as the dimensions of the tree increase.

Here, we will take a look at an algorithm that can be used to convert a tree with any dimensions into a list or array.

For the sake of simplicity, let's look at the following tree:

Each node of this tree can have any number of children.

Tree Structure

Given below is the structure of the tree node:

class Node
   {
       public Node()
       {
           Children = new List<Node>();
       }
       public Node(string data)
           : this()
       {
           Data = data;
       }
       //data
       public string Data { get; set; }
       //children
       public List<Node> Children { get; set; }
   }

Approach

We will solve the problem with the following approach:

1. Starting with the root node, we will assign index to every node (in the DFS manner). This index will represent the index of node within the array or list.
2. By DFS, we mean first we will assign index 0 to the root, then move to its first child and set its index as 1.
3. Then move to child of the first child and set its index to 2 and so on, till we reach the leaf node.
4. Once we reach the leaf node, we move backwards and find the first node with more than 1 child and treat this as root.
5. Repeat steps 2 to 5 until the index of all nodes is set.

Below is the pictorial representation of the algorithm:

Code

Let's create one more class to define the node of the array. We will call it ArrayItem.

class ArrayItem
   {
       public ArrayItem()
       {
           //instantiate list
           ChildrenIndicies = new List<int>();
           ParentIndex = null;
       }

       //data
       public string Data { get; set; }
       //this defines the index of an object within the array or list
       public int Index { get; set; }
       //this defines the index of parent item in the array
       public int? ParentIndex { get; set; }
       // this will contain the indices of children
       public List<int> ChildrenIndicies { get; set; }
       //an additional property to define whether ith node is a leafnode or a node
       public string Type { get; set; }
   }

Magic Method

Here is the method that will convert a tree into a list:

private static void FormListFromTree(Node node, List<ArrayItem> list, int? parentIndex)
       {
           //create an array item from node
           var arrayItem = new ArrayItem()
           {
               //set data property
               Data = node.Data,
               //set type property
               Type = node.Children.Count > 0 ? "Node" : "Leaf",
               //set parent index
               ParentIndex = parentIndex
           };
           //set the index
           arrayItem.Index = list.Count;
           //add object to array
           list.Add(arrayItem);
           //if this is not the root node
           if (parentIndex != null)
           {
               //add child index of current array item to its parent
               list[(int)parentIndex].ChildrenIndicies.Add(arrayItem.Index);
           }
           //do for all children of the node
           for (var i = 0; i < node.Children.Count; i++)
           {
               //recursive call to this method
               FormListFromTree(node.Children[i], list, arrayItem.Index);
           }
       }

Magic Method in Action

Let's create a tree and call the above method to convert it into a list.

static void Main(string[] args)
        {            
            var root = new Node("A");

            //add children(B,C,D) to root A
            root.Children.Add(new Node("B"));
            root.Children.Add(new Node("C"));
            root.Children.Add(new Node("D"));

            //add children (E,F) to B
            root.Children[0].Children.Add(new Node("E"));
            root.Children[0].Children.Add(new Node("F"));

            //add child (G) to C
            root.Children[1].Children.Add(new Node("G"));

            //add child (H) to G
            root.Children[1].Children.Add(new Node("H"));

            //convert the above tree in List
            var arrayItems=new List<ArrayItem>();
            //convert tree to  list
            FormListFromTree(root, arrayItems, null);

            Console.WriteLine(Environment.NewLine);
            Console.WriteLine(Environment.NewLine);
            Console.WriteLine(Environment.NewLine);
            Console.WriteLine("\t\tIndex\tData\tType\tParent\tChildren");
            Console.WriteLine("\t\t \t \t \tIndex\tIndicies");
            Console.WriteLine(Environment.NewLine);
            var parentIdex = "";
            foreach(var arrayItem in arrayItems)
            {
                if(parentIdex==null)
                {

                }
                Console.WriteLine(string.Format("\t\t{0}\t{1}\t{2}\t{3}\t{4}", 
                arrayItem.Index, arrayItem.Data, arrayItem.Type,(arrayItem.ParentIndex == null ? 
                "Null" : arrayItem.ParentIndex.ToString()),
                string.Join(", ", arrayItem.ChildrenIndicies)));
            }

            Console.ReadKey();
        }

Output

Points of Interest

Notice that the Parent Index and Child Indices directly refer to the actual indices of parent and children in the array respectively.