Page 1 of 1

## How sometimes what you require, is a different algorithm. Rate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=315586&amp;s=526fa8376cd3ecea2b87de864f786aaa&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

• MrCupOfT

Reputation: 2285
• Posts: 9,527
• Joined: 29-May 08

Posted 16 March 2013 - 12:36 AM

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)
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.

Is This A Good Question/Topic? 0

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }