Calculate Preorder Tree Traversal From DataTable structure

Question

I have a DataTable that has the following structure:

Root | Level 1 | Level 2 | Level 3 | Tree L | Tree R
Food                                 1        18
       Fruit                         2        11
                 Red                 3        6
                           Cherry    4        5
                 Yellow              7        10
                           Banana    8        9
       Meat                          12       17
                 Beef                13       14
                 Pork                15       16

Using C#, I need to traverse this structure and calculate the correct Tree L and Tree R values for each node. This is just an example, the real structure has several hundred nodes that go out to at least Level 7, but possibly more.

Can anyone suggest how I might approach the code for calculating the left and right values?

Answer 1

So, you want to keep track of the visit order of the tree, but you have the order split into L and R. Those correspond to the "entrance" and "exit" of the Visit function for the Node structure. Assuming a Node class with a Node.Visit() method, you could:

private static List<Tuple<char,Node>> VisitOrder = new List<Tuple<char,Node>>();

public void Visit()
{
    VisitOrder.Add(Tuple.Create('L', this));
    // whatever visit logic you use here
    VisitOrder.Add(Tuple.Create('R', this));
}

When you finish, all you have to do is do is look at the VisitOrder values. They're stored in the List in increasing order, where the index corresponds to it's position in the visit sequence. Each item in the List, then, is a Tuple describing which value it corresponds to and which Node it visited.

Edit:

To get the final output format, you could then do something like:

var LTree = VisitOrder
    .Where(t => t.First == 'L')
    .Select((t, i) => String.Format("{0}) {1}", i + 1, t.Second.Name));
var RTree = VisitOrder
    .Where(t => t.First == 'R')
    .Select((t, i) => String.Format("{0}) {1}", i + 1, t.Second.Name));

Answer 2

Here is how I figured it out:

private class FolderRow
    {
        public int Indent
        {
            get { return this.Row.GetValue("Indent", 0); }
            set { this.Row["Indent"] = value; }
        }
        public int Left
        {
            get { return this.Row.GetValue("Tree L", 0); }
            set { this.Row["Tree L"] = value; }
        }
        public int Right
        {
            get { return this.Row.GetValue("Tree R", 0); }
            set { this.Row["Tree R"] = value; }
        }
        public Guid Id
        {
            get { return this.Row.GetValue("FolderID", Guid.Empty); }

        }
        public DataRow Row { get; private set; }

        public int RowNum { get; set; }

        public bool RowComplete { get { return this.Left > 0 && this.Right > 0; } }

        public FolderRow(DataRow row, int rowNum)
        {
            this.Row = row;
            this.RowNum = rowNum;
        }
    }    

[TestMethod]
public void ImportFolderStructure()
{
    var inputTable = FileUtil.GetDataSetFromExcelFile(new FileInfo(@"c:\SampleTree.xlsx")).Tables[0];

    var currentLevel = 0;
    var nodeCount = 1;
    var currentRow = 0;

    inputTable.Columns.Add("Indent", typeof (int));
    inputTable.Columns.Add("Path", typeof (string));

    var rightStack = new List<FolderRow>();

    foreach (DataRow row in inputTable.Rows)
        row["Indent"] = GetLevelPopulated(row);

    foreach (DataRow row in inputTable.Rows)
    {
        if (row.GetValue("Indent", 0) == 0)
            row["Tree L"] = 1;                

    }

    while (true)
    {
        var row = GetRow(inputTable, currentRow);
        if (row.Indent == 0)
        {
            currentRow++;
            rightStack.Add(row);
            continue; 
        }

        // if the indent of this row is greater than the previous row ...
        if (row.Indent > currentLevel)
        {
            currentLevel++;
            nodeCount++;
            row.Left = nodeCount;
            // ... check the next row to see if it is further indented
            currentRow = HandleNextRow(row, currentRow, rightStack, inputTable, ref currentLevel, ref nodeCount);
        } else if (row.Indent == currentLevel)
        {
            nodeCount++;
            row.Left = nodeCount;
            currentRow = HandleNextRow(row, currentRow, rightStack, inputTable, ref currentLevel, ref nodeCount);
        } else if (row.Indent < currentLevel)
        {
            currentLevel--;
            nodeCount++;
            row.Left = nodeCount;
            currentRow = HandleNextRow(row, currentRow, rightStack, inputTable, ref currentLevel, ref nodeCount);
        }

        if (inputTable.Rows.Cast<DataRow>().Select(r => new FolderRow(r, -1)).All(r => r.RowComplete))
            break;

    }

}

private int HandleNextRow(FolderRow row, int currentRow, List<FolderRow> rightStack, DataTable inputTable, ref int currentLevel,
                          ref int nodeCount)
{
    var nextRow = GetRow(inputTable, currentRow + 1);
    if (nextRow != null)
    {
        if (nextRow.Indent > row.Indent)
        {
            // ok the current row has a child so we will need to set the tree right of that, add to stack
            rightStack.Add(row);
        }
        else if (nextRow.Indent == row.Indent)
        {
            nodeCount++;
            row.Right = nodeCount;
        }
        else if (nextRow.Indent < row.Indent)
        {
            nodeCount++;
            row.Right = nodeCount;
            nodeCount++;
            // here we need to get the most recently added row to rightStack, set the Right to the current nodeCount
            var stackLast = rightStack.LastOrDefault();
            if (stackLast != null)
            {
                stackLast.Right = nodeCount;
                rightStack.Remove(stackLast);
            }

            currentLevel--;
        }

        currentRow++;

        if (rightStack.Count > 1)
        {
            // before we move on to the next row, we need to check if there is more than one row still in right stack and 
            // the new current row's ident is less than the current branch (not current leaf)
            var newCurrentRow = GetRow(inputTable, currentRow);
            var stackLast = rightStack.LastOrDefault();
            if (newCurrentRow.Indent == stackLast.Indent)
            {
                nodeCount++;
                stackLast.Right = nodeCount;
                rightStack.Remove(stackLast);

            }
        }


    }
    else
    {
        // reached the bottom
        nodeCount++;
        row.Right = nodeCount;

        // loop through the remaining items in rightStack and set their right values
        var stackLast = rightStack.LastOrDefault();
        while (stackLast != null)
        {
            nodeCount++;
            stackLast.Right = nodeCount;
            rightStack.Remove(stackLast);
            stackLast = rightStack.LastOrDefault();
        }
    }
    return currentRow;
}

private FolderRow GetRow(DataTable inputTable, int rowCount)
{
    if (rowCount >= inputTable.Rows.Count)
        return null;

    return rowCount < 0 ? null : new FolderRow(inputTable.Rows[rowCount],rowCount);
}

private int GetLevelPopulated(DataRow row)
{
    var level = 0;

    while (level < 14)
    {
        if (level == 0 && row["Root"] != DBNull.Value)
            return level;

        level++;

        if (row["Level " + level] != DBNull.Value)
            return level;
    }

    return -1;
}