26

I have a tree that consists of several objects, where each object has a name (string), id (int) and possibly an array of children that are of the same type. How do I go through the entire tree and print out all of the ids and names?

I'm new to programming and frankly, I'm having trouble wrapping my head around this because I don't know how many levels there are. Right now I'm using a foreach loop to fetch the parent objects directly below the root, but this means I cannot get the children.

Bondolin
  • 2,793
  • 7
  • 34
  • 62
BeefTurkey
  • 900
  • 4
  • 12
  • 13

2 Answers2

55

An algorithm which uses recursion goes like this:

printNode(Node node)
{
  printTitle(node.title)
  foreach (Node child in node.children)
  {
    printNode(child); //<-- recursive
  }
}

Here's a version which also keeps track of how deeply nested the recursion is (i.e. whether we're printing children of the root, grand-children, great-grand-children, etc.):

printRoot(Node node)
{
  printNode(node, 0);
}

printNode(Node node, int level)
{
  printTitle(node.title)
  foreach (Node child in node.children)
  {
    printNode(child, level + 1); //<-- recursive
  }
}
ChrisW
  • 54,973
  • 13
  • 116
  • 224
0

Well, you could always use recursion, but in a "real world" programming scenario, it can lead to bad things if you don't keep track of the depth.

Here's an example used for a binary tree: http://www.codeproject.com/KB/recipes/BinarySearchTree.aspx

I would google linked lists and other tree structures if you're new to the whole data structure thing. There's a wealth of knowledge to be had.

GEOCHET
  • 21,119
  • 15
  • 74
  • 98
Alex Fort
  • 18,459
  • 5
  • 42
  • 51
  • Would you illustrate the alternative to using recursion (i.e. a non-recursive version of my example pseudo-code)? – ChrisW Jan 14 '09 at 16:43
  • 1
    I think it would be a little big and unwieldy. Your example is definitely the simplest, and easiest for him to grasp. I was just trying to stress that recursion is usually a bad idea in a production environment. – Alex Fort Jan 14 '09 at 16:46
  • 1
    If you put in the proper checks to be sure it never infinitately recurses, why is it a bad idea? We use recursion in a couple of places in our production environment but limit the level it recurses. – Tom Anderson Jan 14 '09 at 16:49
  • You need to keep track of the context somehow: so if you're not going to recurse (keeping context on the program stack), then you need to keep it on the heap (perhaps by using a local variable of type `Stack`)? I'm not sure why you say that's "usually a bad idea", assuming any sensibly-depthed tree? – ChrisW Jan 14 '09 at 16:52
  • 1
    If you implement it like Tom Anderson mentioned, by keeping track of the depth and limiting it, then there's no real problem with it. For a new programmer though, it's pretty easy to get into a stack overflow situation. – Alex Fort Jan 14 '09 at 16:54
  • Agree with Tom Anderson. I don't see why it's a bad idea as long as you test for end conditions, i.e. "know when to stop". One thing is to say "beware of infinite recursion" and another is to flat out say that it's usually a bad idea to use in "real world" programming scenerio. – felideon Jan 14 '09 at 17:01
  • @Alex: Cool. Still getting used to the flow here at SO. :) Plus I needed to refresh. – felideon Jan 14 '09 at 17:05
  • Yeah, I know.. comments keep appearing and disappearing it seems :P – Alex Fort Jan 14 '09 at 17:07