LiorA LiorA - 1 month ago 25
C# Question

yield in recursion bst

I've created a templated bst class and I've implemented GetEnumerator but I'm really not happy with what've done.

so first of all I felt i needed an helper function inner visit

private IEnumerable<Node<T>> innerVisit(Node<T> root)
{
if(root== null)
yield break;

if (root.Left != null)
{
var l = innerVisit(root.Left);
foreach (var item in l)
yield return item;
}


yield return root;

if (root.Right != null)
{
var r = innerVisit(root.Right);
foreach (var item in r)
yield return item;
}


}


I really dislike the repeating code but couldn't find a proper solution to it
, clearly repeating the loop is unclean but also I feel that burying it under a function that would jump into this one would be bad practice to say the least. any suggestion on how to do this properly?

also to complete the implementation I've written

public IEnumerator<Node<T>> GetEnumerator()
{

var res = innerVisit(_root);

foreach (var item in res)
yield return item;

}


but that too feels bad and more of a hack to make sure it will work within foreach loop and etc.

Answer

I don't think you can solve your problem without repeating the same operations like you did, but I do think you can do it in a clearer way, it is part of the requirements to return an IEumerable and If you want to do it in a recursive way you can't prevent reapiting the yield operations (but you don't have to write all of them by yourself, System.LINQ will help us with that).

We can replace the foreach and the yield return with Enumerable.Concat method, using it we can concat the left InnerVisit IEnumerable, IEnumerable that we will create for the node itself (an array with 1 item of the current node) and the right InnerVisit IEnumerable:

private IEnumerable<Node<T>> InnerVisit(Node<T> node)
{
    if(node == null)
    {         
        return Enumerable.Empty<Node<T>>;
    }
    return InnerVisit(node.Left).Concat(new[] { node }).Concat(InnerVisit(node.Right));
}

Notice that there is no need to check if Left or Right is null before you call the recursive method because it will check it later in the inner call, if it is null we will return an Enumerable.Empty<Node<T>> instead of using yield break as you did.

We can also simplify GetEnumerator by calling GetEnumerator directly on the result of the root InnerVisit, something like this:

public IEnumerator<Node<T>> GetEnumerator()
{
     return InnerVisit(_root).GetEnumerator();
}