[AdamSpeight2008]

How sometimes what you require, is a different algorithm.


Let's say we have a balance binary tree and we want to yield (iterate) all the nodes in order.

Interface IBalancedTreeNode(Of T)
  ReadOnly Property Value As T
  Property Left As IBalancedTreeNode(Of T)
  Property Righ As IBalancedTreeNode(Of T)
End Interface

Let's take the simple recursive approach

<Extension>
Public Iterator YieldNode(Of T)( node As IBalancedTreeNode(Of T)) As IEnumerable(Of IBalancedTreeNode(Of T))
  IF node Is Nothing Then Exit Function
  For Each node In node.Left.YieldNodes
    Yield node
  Next
  Yield node
  For Each node In node.Righ.YieldNodes
    Yield node
  Next
End Function

Really simple to follow arithmetically , but has the issue that you are repeatedly yielding the same node(s).

---

A Solution would be that have some way of passing as parameter "the yield" when you do the recursion

Imaginary VB.net

extension public iterator function YieldNodes(of T)
  ( node As IBalancedTreeNode(Of T)
  ) As IEnumerable(Of IBalancedTreeNode(Of T))
  return _YieldNodes(of T)( node, ThisMethod.Yielder )
end function

extension private iterator function
  _YieldNodes (Of T)(Node As IBalancedTreeNode(of T),
            ByRef yielder As Yield(Of
                                      IEnumerable(Of IBalancedTreeNode(Of T))
                                  )
                    ) As IEnumerable(Of IBalancedTreeNode(of T))
  If node Is Nothing Then Exit Function
  If node.Left IsNot Nothing Then node.YieldNodes( yielder )
  Yielder.Yield node
  If node.Righ IsNot Nothing Then Node.YieldNodes( yielder )
end function

Now the yield algorithm is Linear, but I have yet to find a way to implement this design.

So this means a change of algorithm to fit in with restrictions of the language.

---

<Extension>
  Iterator Function YieldNodes(Of T)
    ( Current As IBalancedTreeNode(Of T)
    ) As IEnumerable(Of IBalancedTreeNode(Of T))

    If Current IsNot Nothing Then Exit Function
    Dim TheStack As New Stack(Of BalancedTreeNode(Of T) )
 
   Do

      While Current IsNot Nothing
        TheStack.Put( Current )
        Current = Current.Left
      End While

      If TheStack.Count > 0 Then
        Dim Popped = TheStack.Pop
        Yield Popped
        Current = Popped.Righ
      End If

    Loop Until (Current Is Nothing) AndAlso (TheStack.Count = 0)

  End Function

Slightly more complex algorithm to understand, but has the advantage of linearizing the yielding of nodes.

---

Conclusion

Think about how the programming language can effect the implementation of your algorithm.
Also think how the implementation can effect the running time of the algorithm.