using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        var bst = new BinarySearchTree<int>();

        var numbers = new int[] { 4, 2, 6, 1, 3, 5, 7 };

        foreach (var number in numbers)

        {

            bst.Put(number);

        }

​

        var range = bst.Keys(3, 6);

        foreach (var num in range)

        {

            Console.WriteLine(num);

        }

    }

    class BinarySearchTree<T> where T : IComparable

    {

        public Node Root;

​

        public class Node

        {

            public T Key { get; set; }

​

            public Node Left { get; set; }

            public Node Right { get; set; }

​

            public Node(T key)

            {

                Key = key;

            }

        }

​

        public IEnumerable<T> Keys(T low, T high)

        {

            var queue = new Queue<T>();

            Keys(Root, queue, low, high);

            return queue;

        }

​

        private void Keys(Node node, Queue<T> queue, T low, T high)

        {

            if (node == null)

                return;

​

            int cmpLow = low.CompareTo(node.Key);

            int cmpHigh = high.CompareTo(node.Key);

​

            if (cmpLow < 0)

            {

                Keys(node.Left, queue, low, high);

            }

            if (cmpLow <= 0 && cmpHigh >= 0)

            {

                queue.Enqueue(node.Key);

            }    

            if (cmpHigh > 0)

            {

                Keys(node.Right, queue, low, high);

            }

        }

​

        public void Put(T key)

        {

            Root = Put(Root, key);

        }

​

        private Node Put(Node node, T key)

        {

            if (node == null)

            {

                node = new Node(key);

            }

​

            int cmp = key.CompareTo(node.Key);

​

            if (cmp < 0)

            {

                node.Left = Put(node.Left, key);

            }

            else if (cmp > 0)

            {

                node.Right = Put(node.Right, key);

            }

​

            return node;

        }

    }   

}