Efficient implementation of range search

I try to achieve efficient implementation of range search in generic binary search tree,

what i want is at least O(logn) + k , complexity, where k is the range of the search.

i can't achieve it , what i came up for , so far, is only O(n) complexity.

Below is the code of my range search implementation, i can't understand what should i do in order to achieve O(logn) + k , complexity .

I'll appreciate any help.

code:

    public class BinarySearchTree<Tkey, Tvalue> : IEnumerable<Node<Tkey, Tvalue>>
        where Tkey : IComparable<Tkey>
        where Tvalue : IComparable<Tvalue>
    {


        /// <summary>
        /// Gets, the root of the binary search tree
        /// </summary>
        public Node<Tkey, Tvalue> Root { get; private set; }

        /// <summary>
        /// Gets, the count of the nodes in the binary search tree
        /// </summary>
        public int Count { get; private set; }

        /// <summary>
        /// Gets, sets list of nodes(for inner utilization)
        /// </summary>
        private List<Node<Tkey, Tvalue>> NodesList { get; set; }


        /// <summary>
        /// Search nodes in the range of keys
        /// </summary>
        /// <param name="startData">Initial key of the range</param>
        /// <param name="endData">End key of the range</param>
        /// <returns>Collection of the found nodes, otherwise returns empty collection</returns>
        public IEnumerable<Node<Tkey, Tvalue>> SearchInRange(Tkey startData, Tkey endData)
        {
            if (this.Root == null) // if tree is empty
                return null;

            // list to hold the found nodes
            List<Node<Tkey, Tvalue>> nodesList = new List<Node<Tkey, Tvalue>>();

            // utilize the InOrderRangeSearch function which fill the list 
            PreOrderRangeSearch(this.Root, nodesList, startData, endData);

            return nodesList;
        } // end of SearchInRange



        /// <summary>
        /// Runs through the binary search tree's nodes
        /// find the node in the specified range, fill the list
        /// with found nodes
        /// </summary>
        /// <param name="root">Rooth of the binary search tree(start point)</param>
        /// <param name="list">List to fill with found nodes</param>
        /// <param name="startNode">Start point of the range</param>
        /// <param name="endNode">End point of the range</param>
        private void PreOrderRangeSearch(Node<Tkey, Tvalue> root, List<Node<Tkey, Tvalue>> list, Tkey startNode, Tkey endNode)
        {   // if found node is in the range 
            if (root.Key.CompareTo(startNode) >= 0 && root.Key.CompareTo(endNode) <= 0)
                list.Add(root); // adds node to the list

            if (root.Left != null) // if node has left children
                PreOrderRangeSearch(root.Left, list, startNode, endNode);

            if (root.Right != null) // if node has right children
                PreOrderRangeSearch(root.Right, list, startNode, endNode);

        } // end of PreOrderRangeSearch





    }