Generate Nested Menu from datatable using c# as ul list not Asp.net Menu control

Question

I need to generate a custom menu which has submenu's using list ul from the DataTable

Below is the sample of Database and sample HTML ul list with dummy data.

PID         MENU                 Handler                  PageLangID  ParentID    IssueID     CatID       MenuPosition
----------- -------------------- ------------------------ ----------- ----------- ----------- ----------- ------------

6           Business             Category.aspx    1           6           1           16          1
6           Culture              Category.aspx    1           6           1           3           1
6           Economy              Category.aspx    1           6           1           2           1
6           Finance              Category.aspx    1           6           1           19          1
6           Infrastructure       Category.aspx    1           6           1           17          1
6           Lifestyle            Category.aspx    1           6           1           20          1
6           Others               Category.aspx    1           6           1           21          1
6           People               Category.aspx    1           6           1           7           1
6           Politics             Category.aspx    1           6           1           1           1
6           Sports               Category.aspx    1           6           1           4           1
12          1002                  Default.aspx             1           12          3           1           1
12          1003                  Default.aspx             1           12          4           1           1
12          1006                  Default.aspx             1           12          1           1           1
12          1009                  Default.aspx             1           12          5           1           1
1           Home                 Default.aspx             1           0           1           1           10
11          Video                Videos.aspx              1           10          1           1           10
2           About Us             Page.aspx                1           0           1           1           20
5           Articles             Articles.aspx            1           0           1           1           20
6           Categories           Category.aspx    1           0           

DESIRED HTML OUTPUT

<div id="nav-wrapper">
<ul id="nav" class="dropdown dropdown-linear"  >
    <li><span class="dir"><a href="./">Home</a></span></li>
    <li ><span class="dir"><a href="ultimate.linear.html">About Us</a></span>
        <ul >
            <li><a href="./">History</a></li>
            <li><a href="./">Our Vision</a></li>
            <li><a href="./">The Team</a></li>
            <li><a href="./">Clients</a></li>
            <li><a href="./">Testimonials</a></li>
            <li><a href="./">Press</a></li>
            <li><a href="./">FAQs</a></li>
        </ul>
    </li>

    <li class="active" ><span class="dir"><a href="ultimate.linear-active.html">Categories</a></span>
        <ul>
            <li><a href="./">Politics</a></li>
            <li><a href="./">Economy</a></li>
            <li><a href="./">Finance</a></li>
            <li><a href="./">Business</a></li>
            <li><a href="./">Group News</a></li>
            <li><a href="./">Culture</a></li>
            <li><a href="./">Lifestyle</a></li>
            <li><a href="./">Sports</a></li>
            <li><a href="./">Infrastructure</a></li>
            <li><a href="./">Book Review</a></li>   
            <li><a href="./">Others</a></li>                
        </ul>
    </li>
</ul>
</div> 

I don't want to use nested repeater controls. I would appreciate sample code which i can work with.

UPDATED: This code doesn't work, definitely i am doing something wrong

protected void Page_Load(object sender, EventArgs e)
{

    DataSet ds = new DataSet();
    ds = DataProvider.Connect_Select(strSql);
     DataTable dt = ds.Tables[0];

    //dt.Select("ParentID == 0") ;
    var s = GenerateUL(dt.Select("ParentID == 0"));
    Response.Write(s);

}


private string GenerateUL(var menus)
{
    var sb = new StringBuilder();

    sb.AppendLine("<ul>");
    foreach (var menu in menus)
    {
        if (menu.Menus.Any())
        {
            sb.AppendLine("<li>" + menu.Text);
            sb.Append(GenerateUL(menu.Menus.AsQueryable()));
            sb.AppendLine("</li>");
        }
        else
            sb.AppendLine("<li>" + menu.Text + "</li>");
    }
    sb.AppendLine("</ul>");

    return sb.ToString();
}

LATEST UPDATE BASED ON DANI SOLUTION

It seems to work fine with his data sample but when i use it with my actual data it generate StackOverflowException was unhandled.

Below is the screen shot of the error.

Error is generated when it goes into sort of infinate loop where PID=6 My actual data which is show above has 23 records & is result of UNION from different tabel that is the reason i have multiple rows in table where PID=6 i am afraid it will also do same where pid=12.

Even if i catch the exception my website still crash due to this ...

Latest CODE

protected void Page_Load(object sender, EventArgs e)
{
    string strSql = "SELECT DISTINCT PID, MENU, Handler,PageLangID, ParentID,IssueID, CatID,MenuPosition FROM MENUTABLE ";

    DataSet ds = new DataSet();
    ds = DataProvider.Connect_Select(strSql);
    DataTable table = ds.Tables[0];
    DataRow[] parentMenus = table.Select("ParentId = 0");
         var sb = new StringBuilder();
         string unorderedList = GenerateUL(parentMenus, table, sb);
    }

    private string GenerateUL(DataRow[] menu, DataTable table, StringBuilder sb)
    {
    sb.AppendLine("<ul>");

    try
    {

        if (menu.Length > 0)
        {
            foreach (DataRow dr in menu)
            {
                ctr = ctr + 1;
                string handler = dr["Handler"].ToString();
                string menuText = dr["MENU"].ToString();
                string line = String.Format(@"<li><a href=""{0}"">{1}</a>", handler, menuText);
                sb.Append(line);

                string pid = dr["PID"].ToString();

                DataRow[] subMenu = table.Select(String.Format("ParentId = {0}", pid));
                if (subMenu.Length > 0)
                {
                    var subMenuBuilder = new StringBuilder();
                    sb.Append(GenerateUL(subMenu, table, subMenuBuilder));
                }
                sb.Append("</li>");
            }
        }
    }
    catch (Exception ex)
    {
    }

    sb.Append("</ul>");
    return sb.ToString();
}

Update: When i change my query which get me result below then it works fine, but it would be good to make it work on actual data which is shown first in the question.

PID         MENU                 Handler                  PageLangID  ParentID    IssueID     CatID       MenuPosition
----------- -------------------- ------------------------ ----------- ----------- ----------- ----------- ------------
1           Home                 Default.aspx             1           0           1           1           10
2           About Us             Page.aspx                1           0           1           1           20
3           News                 News.aspx                1           0           1           1           30
5           Articles             Articles.aspx            1           0           1           1           20
6           Categories           Category.aspx    1           0           1           1           25

Answer 1

I've created a slightly simpler table structure on my side as we only need the following columns for the sake of example :

1. PID
2. MENU
3. Handler
4. ParentID

Sample data:

As you can see from this example we have a 3 way deep hierarchy for Product and the rest of the items have no children.

Code behind:

The code below does the following:

1. First gets all items with no parents and starts looping through them

2. Checks whether an item is a parent to any node and gets its children recursively.

   protected void Page_Load(object sender, EventArgs e)
   {
       DataSet ds = new DataSet();
       ds = DataProvider.Connect_Select("SELECT * FROM Menu");
       DataTable table = ds.Tables[0];
       DataRow[] parentMenus = table.Select("ParentId = 0");
   
       var sb = new StringBuilder();
       string unorderedList = GenerateUL(parentMenus, table,sb);
       Response.Write(unorderedList);
   }
   
   private string GenerateUL(DataRow[] menu,DataTable table,StringBuilder sb)
   {
       sb.AppendLine("<ul>");
   
       if (menu.Length > 0)
       {
           foreach (DataRow dr in menu)
           {
               string handler = dr["Handler"].ToString();
               string menuText = dr["MENU"].ToString();
               string line = String.Format(@"<li><a href=""{0}"">{1}</a>",handler,menuText);
               sb.Append(line);
   
               string pid = dr["PID"].ToString();
   
               DataRow[]subMenu = table.Select(String.Format("ParentId = {0}", pid));
               if (subMenu.Length > 0)
               {
                   var subMenuBuilder = new StringBuilder();
                   sb.Append(GenerateUL(subMenu, table, subMenuBuilder));
               }
               sb.Append("</li>");
           }
       }
   
       sb.Append("</ul>");
       return sb.ToString();
   }
   

End result:

EDIT:

The problem is that the code constructs the menu based on ParentID's and for ID=6 the ParentID also happens to be 6. So 6 calls 6 and we have an endless loop,great.

Now that we know what the issue is, we can put in a simple check to construct sub menus recursively only if ParentId != PID , here's the updated code:

private string GenerateUL(DataRow[] menu, DataTable table, StringBuilder sb)
{
    sb.AppendLine("<ul>");

    if (menu.Length > 0)
    {
        foreach (DataRow dr in menu)
        {
            string handler = dr["Handler"].ToString();
            string menuText = dr["MENU"].ToString();
            string line = String.Format(@"<li><a href=""{0}"">{1}</a>", handler, menuText);
            sb.Append(line);

            string pid = dr["PID"].ToString();
            string parentId = dr["ParentId"].ToString();

            DataRow[] subMenu = table.Select(String.Format("ParentId = {0}", pid));
            if (subMenu.Length > 0 && !pid.Equals(parentId))
            {
                var subMenuBuilder = new StringBuilder();
                sb.Append(GenerateUL(subMenu, table, subMenuBuilder));
            }
            sb.Append("</li>");
        }
    }
    sb.Append("</ul>");
    return sb.ToString();
}

I think the important thing here is to actually understand how this code works by stepping through it in the debugger, that way you'll be able to change if any other issues come up.