c# - BinaryTree の範囲検索を調整して外部要素を取得する

Question

RedBlack [Balanced, sorted] Binary Tree があり、範囲 [lower, upper] 内のすべての値を検索しています。

public IEnumerable<TData> Range(
      BinaryTree<TData> root, 
      IComparer<TData> comparer, 
      TData lower, 
      TData upper)
{
    var stack = new Stack<State>(16);
    BinaryTree<TData> here = root;

    do
    {
        if (here == null)
        {
            if (stack.Count == 0)
                break;

            State popped = stack.Pop();
            yield return popped.Data;
            here = popped.Next;
            continue;
        }

        if (comparer.Compare(here.Data, lower) < 0)
        {
            here = here.Right;
        }
        else if (comparer.Compare(here.Data, upper) > 0)
        {
            here = here.Left;
        }
        else
        {
            stack.Push(new State {Next = here.Right, Data = here.Data});
            here = here.Left;
        }
    } while (true);  
}

したがって、このコードで、値を使用してツリーを構築する場合

 [0, 1, 4, 5, 6, 9], 

範囲内のすべての要素を検索します

 [3, 8]

次の結果が得られます。

 [4, 5, 6]. 

私の質問は、検索の外側の要素を取得するためにこのアルゴリズムを調整するにはどうすればよいですか? このような：

 [1, 4, 5, 6, 9]

つまり、値 3 はツリーの 1 と 4 の間にあるので、1 を返したいと思います。同様に、値 8 は 6 と 9 の間にあり、値 9 を結果に含めたいと思います。

問題の 1 つは、ルートから検索を再開したくないことです。

現在 NGenerics を使用して実装されています

[編集]

一般的なアルゴリズムの回答を喜んで受け入れます。