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<=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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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)$.
-
$\begingroup$ I see, Now I get it, I was confusing the range of nodes to be visited, to each one of the nodes, but I see why that's redundant all we would need is the end points of the range and since an inorder traversal can be done in
O(k)the two have to be added, of course. It was so silly of me. Thanks for the answer. $\endgroup$ May 24, 2021 at 13:56