Question about 15.18 in 1.4.7

#1

Hi,

The problem asks to return a list of all keys in [L, U]. It doesn’t ask the list to be sorted. Isn’t the solution overkilling? Can we just do a traverse instead? If current->data < L, traverse in right subtree only; if current->data > U, traverse in left subtree only; otherwise output current and recursively do the same for left and right. Worse case each node is checked only once, still better than the solution which goes down the tree to find the first node and then come back up when searching for successors, visiting h nodes twice.

Thanks,
Ray

0 Likes
#2

Hey Ray,

First of all, thanks for your reply. Your question is a great question which I personally thought that before. Like you said, we did not emphasize that the output must be in sorted order, and we will put that in the constraint in the later version. In fact, your algorithm with small tuning can also printed sorted answer, without increasing time and space complexities, and I would like to leave that as a homework to you.

Let’s back to our algorithm, there is one important benefit using this. First, in modern programming languages, if we use built-in BST (e.g., map in C++), the two main operations in our algorithm, FindFirstLargerEqualK() and FindSuccessorBST() can be easily performed by the built-in methods (lower_bound() and operator++ in C++ map). Therefore, what you only need to do it a simple for-loop, which definitely is better than recursively traversing the tree. Moreover, recursive function calls will induce unnecessary stack usage which iterative function won’t induce.

Please let us know what you think, and we really appreciate your feedback (a good question indeed).

Tsung-Hsien

0 Likes
#3

Yep it makes sense. Thanks a lot for your reply Tsung-Hsien!

0 Likes