For a balanced binary search tree what is the worst case case time complexity for accessing all elements within a range of nodes? I have this question which is asking for the worst case time complexity for a balanced binary search tree, assume the nodes are labeled as integers and we consider a range of [nodex, nodey], nodex&lt;=nodey. And also given that the range has exactly  k nodes, k can be at most n ie. total number of nodes. The question asks what is the worst case time complexity of accessing all the
k nodes in given range. According to my knowledge of Time-Complexiy analysis It must be O(k*log(n)) since there are k elements and each element takes O(log(n)) time in worst case ( since the tree is balanced ) this seems very plausible, However the answer seems to be O(k + log(n)), what am I doing wrong?
One way to do it is to construct the tree containing those values:

Explore the BST until you find the root of a subtree that is between the bounds;
Explore the left part of the subtree, and trim branches on the left that have a root $\leqslant node_x$;
Do the same thing on the right for roots $\geqslant node_y$

Each of those steps are done in $O(\log n)$ since the BST is balanced. Once you have constructed the tree, just do a tree traversal (in-order for example) of it. This last step is indeed done in $O(k)$.