Nested Loop Question..Easy one.

copyPasteGhost
copyPasteGhost used Ask the Experts™
on
Hello,

This might be very simple, but I seem to be missing something..

I have this type of tree structure:

Root
   Parent
      child
      child
         grandchild
  Parent
    child
      grandchild
        grandgrandchild
  Parent

Basically n parents and n deep.

I'm trying to write a loop that will print out this structure. So far I have this.

foreach(Query database and get all items where the parent == root) {
   print out the parent item.
   check if it has children
   if(has children) {
      print out the child
      foreach(children of the child){
         print them out.
         HERE IS THE PROBLEM HOW CAN I GO "N" DEEP WITHOUT HAVING "N" NESTED LOOPS?

      }
   }

}


Thanks.
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
You *must* use a loop? It would be much easier with recursion, which is the standard way of iterating trees. Check the wikipedia entry, it has pseudocode for inorder, preorder, and postorder traversal:

http://en.wikipedia.org/wiki/Tree_traversal

I attached a simple recursive pseduocode snippet that should get you started.


// print node and all children of that node
void PrintTree(Node n)
{
   foreach(child c of n) PrintTree(c);
   Console.WriteLine(n.ToString());
}

Open in new window

Author

Commented:
ok recursion was what I meant.

if you look at my sample you will see that's what I'm doing..

for your example. what if "child c" has children? then what?
Fernando SotoRetired
Distinguished Expert 2017

Commented:
Hi copyPasteGhost;

You can as you stated use recursion to solve this problem. The code sample below gives an example using a user defined class as elements of the tree and will print out the following.

 Parent1
      Child1
      Child2
           Grandchild1
 Parent2
      Child1
           Grandchild1
                Grandgrandchild1
 Parent3

Fernando
public partial class Form1 : Form
{
    public Form1()
    {
        InitializeComponent();
    }
 
    List<MyTreeStructure> Root = new List<MyTreeStructure>();
 
    private void button1_Click(object sender, EventArgs e)
    {
        // Create Tree structure
        //Parent 1
        MyTreeStructure parent1 = new MyTreeStructure("Parent1", "Parent", null);
        Root.Add(parent1);
        MyTreeStructure child1 = new MyTreeStructure("Child1", "Child", null);
        parent1.Descendent.Add(child1);
        MyTreeStructure child2 = new MyTreeStructure("Child2", "Child", null);
        parent1.Descendent.Add(child2);
        MyTreeStructure gChild1 = new MyTreeStructure("Grandchild1", "Grandchild", null);
        child2.Descendent.Add(gChild1);
        //Parent 2
        MyTreeStructure parent2 = new MyTreeStructure("Parent2", "Parent", null);
        Root.Add(parent2);
        MyTreeStructure child21 = new MyTreeStructure("Child1", "Child", null);
        parent2.Descendent.Add(child21);
        MyTreeStructure gchild22 = new MyTreeStructure("Grandchild1", "Grandchild", null);
        child21.Descendent.Add(gchild22);
        MyTreeStructure ggChild1 = new MyTreeStructure("Grandgrandchild1", "Grandgrandchild1", null);
        gchild22.Descendent.Add(ggChild1);
        //Parent 3
        MyTreeStructure parent3 = new MyTreeStructure("Parent3", "Parent", null);
        Root.Add(parent3);
    }
 
    private void button2_Click(object sender, EventArgs e)
    {
        // Iterate through the parents 
        foreach (MyTreeStructure node in Root)
        {
            // Print the parents sub tree
            PrintTree(node);
        }
    }
 
    int indent = 1;
    
    private void PrintTree(MyTreeStructure node)
    {
        Console.WriteLine("{0," + indent.ToString() + "}{1}", " ", node.Name);
        if (node.Descendent != null)
        {
            indent += 5;
            foreach (MyTreeStructure child in node.Descendent)
            {
                // This is a recursive call to itself
                PrintTree(child);
            }
            indent -= 5;
        }
    }
}
 
// The objects that make up the tree
public class MyTreeStructure
{
    public string Name;
    public string Type;
    public List<MyTreeStructure> Descendent = new List<MyTreeStructure>();
    public MyTreeStructure(string name, string type, MyTreeStructure descendent)
    {
        Name = name;
        Type = type;
        if(descendent != null)
            Descendent.Add(descendent);
    }
}

Open in new window

Amazon Web Services

Are you thinking about creating an Amazon Web Services account for your business? Not sure where to start? In this course you’ll get an overview of the history of AWS and take a tour of their user interface.

Extending from Fippy's post, his method "PrintTree" takes a parameter which determines which node to print.  This assumes that both the root node and all subsequent child nodes are represented by or inherit from the same base object.

The PrintTree routine prints out whatever properties you are interested in and then calls itself on the passed node.  Initially, the root node is passed.  In doing so, the child nodes are iterated and then passed to a new run of the PrintTree routine.  If a child has its own children, the PrintTree routine is called again passing those and so on.

My code sample below differs slightly from Fippy's.  His prints the current node after iterating the children and mine prints the current node before iterating the children (this is usually what I want to happen, YMMV).

In my code, the following happens:

    PrintTree(tree)             --> prints "tree"
    PrintTree(child1)          --> prints "--child1"
    PrintTree(gchild1a)      --> prints "----gchild1a"
    PrintTree(ggchild1ai)   --> prints "------ggchild1ai"
    PrintTree(gchild1b)      --> prints "----gchild1b"
    PrintTree(child2)          --> prints "--child2"
    PrintTree(gchild2a)      --> prints "----gchild2a"    
    PrintTree(gchild2b)      --> prints "----gchild2b"

If ggchild1ai has a child, the PrintTree method would call itself again, passing that child.  This is the founding principal of recursion -- because the method calls itself with another parameter, exactly the same thing will happen as happened to all the other nodes.

J.

    public class Node 
    {
        private readonly List<Node> children = new List<Node>();
        private readonly string foo;
 
        public Node(string foo) { this.foo = foo; }
 
        public string Foo { get; set; }
        public ICollection<Node> Children { get { return children; } }
    }
 
    public static class Program
    {
        public static int Main(string[] args)
        {
            // create tree
            Node tree = new Node("tree");
            Node child1 = new Node("child1");
            Node child2 = new Node("child2");
            Node gchild1a = new Node("gchild1a");
            Node gchild1b = new Node("gchild1b");
            Node gchild2a = new Node("gchild2a");
            Node gchild2b = new Node("gchild2b");
            Node ggchild1ai = new Node("ggchild1ai");
 
            tree.Children.Add(child1);
            tree.Children.Add(child2);
            child1.Children.Add(gchild1a);
            child1.Children.Add(gchild1b);
            child2.Children.Add(gchild2a);
            child2.Children.Add(gchild2b);
            gchild1a.Children.Add(ggchild1ai);
 
            // start recursion
            PrintTree(tree);
        }
 
        private int printIndent = 0;
 
        private void PrintTree(Node n)
        {
            Console.Write('-', printIndent);
            Console.WriteLine(n.Foo);
            printIndent++;
            foreach (Node c in n.Children) PrintTree(c);
            printIndent--;
        }
    }

Open in new window

Author

Commented:
Perhaps my question was not structured right..

I've got what I want working... but it's not dynamic... You will see immediatly what I mean..

Check out the sample code... this is what I'm looking for...
void FillMainCats(TreeNode node) {
      foreach (Category oCategory in Category.GetAllRootLevelCategories()) {
         string sCatName = (from c in oCategory.LangIDCats where c.LangID == "en_US" select c.DisplayName).SingleOrDefault();
         if (sCatName != null) {
            TreeNode oParentNode = new TreeNode(sCatName, oCategory.Code);
            oParentNode.SelectAction = TreeNodeSelectAction.Expand;
            List<Category> oChildCats = Category.GetAllChildCats(oCategory.id);
            while (oChildCats.Count != 0) {
               foreach (Category oChildCat in oChildCats) {
                  TreeNode oChildNode = new TreeNode((from c in oChildCat.LangIDCats where c.LangID == "en_US" select c.DisplayName).SingleOrDefault(), oChildCat.Code);
                  oChildNode.SelectAction = TreeNodeSelectAction.Expand;
                  oParentNode.ChildNodes.Add(oChildNode);
                  oChildCats = Category.GetAllChildCats(oChildCat.id);
                  while (oChildCats.Count != 0) {
                     foreach (Category oGrandChildCat in oChildCats) {
                        TreeNode oGrandChildNode = new TreeNode((from c in oGrandChildCat.LangIDCats where c.LangID == "en_US" select c.DisplayName).SingleOrDefault(), oGrandChildCat.Code);
                        oGrandChildNode.SelectAction = TreeNodeSelectAction.Expand;
                        oChildNode.ChildNodes.Add(oGrandChildNode);
                        oChildCats = Category.GetAllChildCats(oGrandChildCat.id);
                        while (oChildCats.Count != 0) {
                           foreach (Category oGGChildCat in oChildCats) {
                              TreeNode oGGChildNode = new TreeNode((from c in oGGChildCat.LangIDCats where c.LangID == "en_US" select c.DisplayName).SingleOrDefault(), oGrandChildCat.Code);
                              oGGChildNode.SelectAction = TreeNodeSelectAction.Expand;
                              oGrandChildNode.ChildNodes.Add(oGGChildNode);
                              oChildCats = Category.GetAllChildCats(oGGChildCat.id);
                              while (oChildCats.Count != 0) {
                                 foreach (Category oGGGChildCat in oChildCats) {
                                    TreeNode oGGGChildNode = new TreeNode((from c in oGGGChildCat.LangIDCats where c.LangID == "en_US" select c.DisplayName).SingleOrDefault(), oGrandChildCat.Code);
                                    oGGGChildNode.SelectAction = TreeNodeSelectAction.Expand;
                                    oGGChildNode.ChildNodes.Add(oGGGChildNode);
                                    oChildCats = Category.GetAllChildCats(oGGGChildCat.id);
                                    while (oChildCats.Count != 0) {
                                       foreach (Category oGGGGChildCat in oChildCats) {
                                          TreeNode oGGGGChildNode = new TreeNode((from c in oGGGGChildCat.LangIDCats where c.LangID == "en_US" select c.DisplayName).SingleOrDefault(), oGrandChildCat.Code);
                                          oGGGGChildNode.SelectAction = TreeNodeSelectAction.Expand;
                                          oGGGChildNode.ChildNodes.Add(oGGGGChildNode);
                                          oChildCats = Category.GetAllChildCats(oGGGGChildCat.id);
                                       }
                                    }
                                 }
                              }
                           }
                        }
                     }
                  }
               }
            }
            node.ChildNodes.Add(oParentNode);
         }
      }
   }

Open in new window

>> foreach(Query database and get all items where the parent == root)
This leads to a more interesting problem.  Namely, can you afford the hit of going back to the database to get the children, inside the loop?

You will probably find that going to the database once for each child adds a significant overhead to your program.  It may be preferable to retrieve all of the tree'd data from the database and iterate through the rows.

Depending on your database of choice, there will be a different way of doing this (e.g. SQL Server 2005+ uses the WITH statement, Oracle uses the CONNECT BY statement).  

If you need it to be database agnostic, you need to refactor the database tree to use Joe Celko's nested set principal (http://www.intelligententerprise.com/001020/celko.jhtml).

J.
>> I've got what I want working... but it's not dynamic... You will see immediatly what I mean..
See all other posts...

Author

Commented:
The category object is cached locally. That will not be a issue. The problem I'm running into is that if I have a 10 level deep category according to the code I just posted I will need to have 10 nested loops.

There must be a better way to do it. I just can't seem to figure it out right now...thus the question :)

Author

Commented:
the building of the tree is static in all the examples. I need something dynamic.
It will look something like this (untested).

J.
void FillMainCats()
{
	foreach (Category rootCat in Category.GetAllRootLeveCategories())
		FillTree(theTreeViewControl.Nodes, rootCat);
}
 
void FillTree(TreeNodeCollection nodes, Category category)
{
	string displayName = (from c in category.LangIDCats where c.LangID == "en_US" select c.DisplayName).SingleOrDefault();
	TreeNode newNode = new TreeNode(displayName, category.Code);
	newNode.SelectAction = TreeNodeSelectAction.Expand;
	
	nodes.Add(newNode);
	
	foreach (Category childCat in category.GetAllChildCats(category.id))
		FillTree(newNode.ChildNodes, childCat);
}

Open in new window

Author

Commented:
exactly! thanks.

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial