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;
}
public string Data { get; set; }
public List<Node> Children { get; set; }
}
Approach
We will solve the problem with the following approach:
- 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.
- 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.
- Then move to child of the first child and set its index to 2 and so on, till we reach the leaf node.
- Once we reach the leaf node, we move backwards and find the first node with more than 1 child and treat this as root.
- 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()
{
ChildrenIndicies = new List<int>();
ParentIndex = null;
}
public string Data { get; set; }
public int Index { get; set; }
public int? ParentIndex { get; set; }
public List<int> ChildrenIndicies { get; set; }
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)
{
var arrayItem = new ArrayItem()
{
Data = node.Data,
Type = node.Children.Count > 0 ? "Node" : "Leaf",
ParentIndex = parentIndex
};
arrayItem.Index = list.Count;
list.Add(arrayItem);
if (parentIndex != null)
{
list[(int)parentIndex].ChildrenIndicies.Add(arrayItem.Index);
}
for (var i = 0; i < node.Children.Count; i++)
{
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");
root.Children.Add(new Node("B"));
root.Children.Add(new Node("C"));
root.Children.Add(new Node("D"));
root.Children[0].Children.Add(new Node("E"));
root.Children[0].Children.Add(new Node("F"));
root.Children[1].Children.Add(new Node("G"));
root.Children[1].Children.Add(new Node("H"));
var arrayItems=new List<ArrayItem>();
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.