In-order tree traversal

program InOrderTraversal;

{$APPTYPE CONSOLE}

uses
  SysUtils;

type
  TNodeEnumerator<T> = class;

  TNode<T> = class
  strict private
    fLeft, fRight, fParent: TNode<T>;
    fValue: T;
  public
    constructor Create(const value: T; left, right: TNode<T>);
    destructor Destroy; override;

    function InOrder: TNodeEnumerator<T>;

    property Left: TNode<T> read fLeft;
    property Right: TNode<T> read fRight;
    property Parent: TNode<T> read fParent;
    property Value: T read fValue;
  end;

  TNodeEnumerator<T> = class
  protected
    fNode: TNode<T>;
    fStarted: Boolean;
    function GetCurrent: T;
  public
    constructor Create(node: TNode<T>);
    function GetEnumerator: TNodeEnumerator<T>;
    function MoveNext: Boolean; virtual;
    property Current: T read GetCurrent;
  end;

  TInOrderEnumerator<T> = class(TNodeEnumerator<T>)
  private
    function Next(node: TNode<T>): TNode<T>;
  public
    function MoveNext: Boolean; override;
  end;

{ TNode<T> }

constructor TNode<T>.Create(const value: T; left, right: TNode<T>);
begin
  fValue := value;
  fLeft := left;
  if Assigned(fLeft) then
    fLeft.fParent := Self;
  fRight := right;
  if Assigned(fRight) then
    fRight.fParent := Self;
end;

destructor TNode<T>.Destroy;
begin
  fLeft.Free;
  fRight.Free;
  inherited;
end;

function TNode<T>.InOrder: TNodeEnumerator<T>;
begin
  Result := TInOrderEnumerator<T>.Create(Self);
end;

{ TNodeEnumerator<T> }

constructor TNodeEnumerator<T>.Create(node: TNode<T>);
begin
  fNode := node;
end;

function TNodeEnumerator<T>.GetCurrent: T;
begin
  Result := fNode.Value;
end;

function TNodeEnumerator<T>.GetEnumerator: TNodeEnumerator<T>;
begin
  Result := Self;
end;

function TNodeEnumerator<T>.MoveNext: Boolean;
begin
  Result := False;
end;

{ TInOrderEnumerator<T> }

function TInOrderEnumerator<T>.Next(node: TNode<T>): TNode<T>;
begin
  if Assigned(node.Right) then
  begin
    Result := node.Right;
    while Assigned(Result.Left) do
      Result := Result.Left;
  end
  else
  begin
    Result := node.Parent;
    while Assigned(Result) do
    begin
      if Result.Left = node then
        Break;
      node := Result;
      Result := node.Parent;
    end;
  end;
end;

function TInOrderEnumerator<T>.MoveNext: Boolean;
begin
  if not Assigned(fNode) then
    Exit(False);
  if not fStarted then
  begin
    while Assigned(fNode.Left) do
      fNode := fNode.Left;
    fStarted := True;
  end
  else
    fNode := Next(fNode);
  Result := Assigned(fNode);
end;

procedure Main;
var
  root: TNode<Integer>;
  i: Integer;
begin
  root := TNode<Integer>.Create(1,
    TNode<Integer>.Create(2,
      TNode<Integer>.Create(4,
        TNode<Integer>.Create(7, nil, nil),
        nil),
      TNode<Integer>.Create(5, nil, nil)
    ),
    TNode<Integer>.Create(3,
      TNode<Integer>.Create(6,
        TNode<Integer>.Create(8, nil, nil),
        TNode<Integer>.Create(9, nil, nil)
      ), nil
    )
  );

  for i in root.InOrder do
    Writeln(i);

  root.Free;
end;

begin
  try
    Main;
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
  Readln;
  ReportMemoryLeaksOnShutdown := True;
end.