12

I have a recursive function that returns all subtree nodes, given the starting root node.

private IEnumerable<Node> getAllNodesRecursively(Node subnode)
{
    foreach (Node node in subnode.Nodes)
        getAllNodesRecursively(node);

    yield return subnode;
}

For the following tree structure:

A
|
+--B
|
+--C
|  |
|  +--D
|
+--E

When I try to iterate as such:

foreach (Node n in getAllNodesRecursively(a))
{
    Console.WriteLine(n);
}

the function returns the only the A value.

I wish to use yield-return with recursion and retrieve elements in the Preorder (A, B, C, D, E in this example).

(If I put the yield return before the foreach, the foreach would never happen).

Is this possible?

Kornelije Petak
  • 9,412
  • 15
  • 68
  • 96
  • Did you try that the foreach is not called if you put the yield return in front? I guess it will be called. – okrumnow Feb 03 '12 at 09:55
  • Yes, you were right. Yield return does not skip the rest of the code. It seems it's just a syntactic sugar to allow value return and still keep the function running. My bad. – Kornelije Petak Feb 03 '12 at 10:24

3 Answers3

19

Have you tried something like:

private IEnumerable<Node> getAllNodesRecursively(Node subnode) 
{ 
    // Return the parent before its children
    yield return subnode; 

    foreach (Node node in subnode.Nodes) 
    {
        foreach(Node n in getAllNodesRecursively(node))
        {
            yield return n;
        }
    }
}

Your implementation is calling getAllNodesRecursively recursively, but ignoring its return value.

Joe
  • 122,218
  • 32
  • 205
  • 338
  • This works, but why do I have to iterate again (inner foreach)? Why does the iterator method does not allow recursion as it is? I've tried with the debugger and it simply skipped my recursive call unless it's used in an iteration (such as foreach). Why is that? – Kornelije Petak Feb 03 '12 at 10:20
  • @ChristianHayter "Won't that return all except the top node twice?" No. – Joe Feb 03 '12 at 10:28
  • 1
    Joe's example can by a little simplified: private IEnumerable getAllNodesRecursively(Node root) { yield return root; foreach (var child in root.Nodes.SelectMany(getAllNodesRecursively)) { yield return child; } } – peter70 Jul 24 '14 at 09:55
3

You need to explicitly iterate + yield return the nodes of children of each node ala:

        public IEnumerable<int> preOrder(Node root)
        {
            if (root == null)
                yield break;

            yield return root.val;

            if (root.left != null)
                foreach (int i in preOrder(root.left))
                    yield return i;

            if (root.right != null)
                foreach (int i in preOrder(root.right))
                    yield return i;
        }
XDS
  • 3,786
  • 2
  • 36
  • 56
Lee.O.
  • 63
  • 5
  • While this code snippet may solve the question, [including an explanation](http://meta.stackexchange.com/questions/114762/explaining-entirely-code-based-answers) really helps to improve the quality of your post. Remember that you are answering the question for readers in the future, and those people might not know the reasons for your code suggestion. – lokusking Aug 14 '16 at 12:06
3

Yes it's possible, just put the yield return before the foreach. You are thinking of the behaviour of a normal return statement.

Christian Hayter
  • 30,581
  • 6
  • 72
  • 99