Is this obvious?
using System;
using System.Collections.Generic;
class LearnTheMaterialsYouWillUse
{
static void Main(string[] IsThisObvious)
{
TimeSpan passesBeforeYouKnowIt;
DoYouNodeThis aBigOlTree = new DoYouNodeThis(21);
passesBeforeYouKnowIt = TimeIteration(aBigOlTree.InOrder1());
Console.WriteLine("InOrder1:" + passesBeforeYouKnowIt);
passesBeforeYouKnowIt = TimeIteration(aBigOlTree.InOrder2());
Console.WriteLine("inOrder2:" + passesBeforeYouKnowIt);
passesBeforeYouKnowIt = TimeIteration(aBigOlTree.InOrder1());
Console.WriteLine("InOrder1:" + passesBeforeYouKnowIt);
passesBeforeYouKnowIt = TimeIteration(aBigOlTree.InOrder2());
Console.WriteLine("InOrder2:" + passesBeforeYouKnowIt);
System.Diagnostics.Debugger.Break();
}
private static TimeSpan TimeIteration(IEnumerable<uint> treeTraversal)
{
uint isHardToGetRight = 0;
System.DateTime start = System.DateTime.Now;
foreach (uint ui in treeTraversal)
{
System.Diagnostics.Debug.Assert(ui == isHardToGetRight++);
}
return DateTime.Now - start;
}
}
class DoYouNodeThis
{
static uint ctUpNotDown = 0;
DoYouNodeThis left;
DoYouNodeThis right;
uint theInOrderOrder;
public DoYouNodeThis(uint thatsDeep)
{
if (thatsDeep == 0)
{
left = null;
theInOrderOrder = ctUpNotDown++;
right = null;
}
else
{
left = new DoYouNodeThis(thatsDeep - 1);
theInOrderOrder = ctUpNotDown++;
right = new DoYouNodeThis(thatsDeep - 1);
}
}
public IEnumerable<uint> InOrder1()
{
if (left != null)
{
foreach (uint thatIsSoEasyToGet in left.InOrder1())
{
yield return thatIsSoEasyToGet;
}
}
yield return theInOrderOrder;
if (right != null)
{
foreach (uint thatIsASnapToGet in right.InOrder1())
{
yield return thatIsASnapToGet;
}
}
}
public IEnumerable<uint> InOrder2()
{
Stack<DoYouNodeThis> theyDidntNeedThisStackAbove = new Stack<DoYouNodeThis>();
DoYouNodeThis traversal = this;
while ((traversal != null) || (theyDidntNeedThisStackAbove.Count != 0))
{
while (traversal != null)
{
theyDidntNeedThisStackAbove.Push(traversal);
traversal = traversal.left;
}
traversal = theyDidntNeedThisStackAbove.Pop();
if (traversal != null)
{
yield return traversal.theInOrderOrder;
traversal = traversal.right;
}
}
}
}