Question

How to parse a table into a binary tree in C#

Answer 1

using System;
using System.Collections.Generic;

public class Node
{
    public int Id { get; }
    public string Name { get; }

    public Node Left;
    public Node Right;

    public Node(int id, string name)
    {
        Id = id;
        Name = name;
    }
}

public static class TreePrinter
{
    public static void Print(Node root, int depth = 0)
    {
        if (root == null) return;

        // Print ROOT on its own line
        if (depth == 0) {
            Console.WriteLine("ROOT");
        }

        // Indent the node itself
        for (int i = 0; i < depth + 1; i++)
            Console.Write("  ");

        Console.WriteLine($"{root.Id:00} - {root.Name}");

        // Print children
        Print(root.Left, depth + 1);

        // Print next top-level sibling
        if (depth == 0 && root.Right != null) {
            Print(root.Right, 0);   // restart at ROOT
        }
        else {
            Print(root.Right, depth);
        }
    }
}

public static class TreeBuilder
{
    public static Node BuildTree(
        List<(int Id, string Name, int ParentId)> table,
        Dictionary<int, Node> nodesOut)
    {
        foreach (var row in table)
        {
            nodesOut[row.Id] = new Node(row.Id, row.Name);
        }

        Node root = null;

        foreach (var row in table)
        {
            Node current = nodesOut[row.Id];

            if (row.ParentId == 0)
            {
                if (root == null) {
                    root = current;
                }
                else {
                    Node p = root;
                    while (p.Right != null)
                        p = p.Right;
                    p.Right = current;
                }
            }
            else
            {
                Node parent = nodesOut[row.ParentId];

                if (parent.Left == null)
                {
                    parent.Left = current;
                }
                else
                {
                    Node p = parent.Left;
                    while (p.Right != null)
                        p = p.Right;
                    p.Right = current;
                }
            }
        }

        return root;
    }
}

public class Program
{
    public static void Main()
    {
        var table = new List<(int Id, string Name, int ParentId)>
        {  // Id  Name            ParentId 
            ( 1, "Node 1",        0),
            ( 2, "Node 1.1",      1),
            ( 3, "Node 2",        0),
            ( 4, "Node 1.1.1",    2),
            ( 5, "Node 2.1",      3),
            ( 6, "Node 2.3.1",    3),
            ( 7, "Node 1.2",      1),
            ( 8, "Node 1.3",      1),
            ( 9, "Node 1.3.1",    8),
            (10, "Node 2.4",      3),
            (11, "Node 2.1.1",    5),
            (12, "Node 2.1.1.6", 11)
        };

        var nodes = new Dictionary<int, Node>();
        Node root = TreeBuilder.BuildTree(table, nodes);

        TreePrinter.Print(root);
    }
}


/*
run:

ROOT
  01 - Node 1
    02 - Node 1.1
      04 - Node 1.1.1
    07 - Node 1.2
    08 - Node 1.3
      09 - Node 1.3.1
ROOT
  03 - Node 2
    05 - Node 2.1
      11 - Node 2.1.1
        12 - Node 2.1.1.6
    06 - Node 2.3.1
    10 - Node 2.4

*/

 

70+ SQL courses for beginners and professionals