Recursion with yield return elements order in tree

11
votes

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?

3
c#recursiontreeyield-returnpostorder
Did you try that the foreach is not called if you put the yield return in front? I guess it will be called. – okrumnow
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

3 Answers

17
votes

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.

3
votes

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

3
votes

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;
        }