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.