Binary search tree

[sarajan82@gmail.com]

Hi all,

Given a binary search tree and a number n, how can we find the
smallest node of the tree greater than n and the largest node smaller
than n?
For example for the following binary search tree where 5 is root and 4
is the left and 6 the right child, for an input of 5,
4 and 6 will be output:

5
4 6

Thanks,
Sara

[David Harmon]

Re: Binary search tree

On Sun, 25 Nov 2007 03:29:33 -0800 (PST) in comp.lang.c++,
sarajan82@gmail .com wrote,

>Given a binary search tree and a number n, how can we find the
>smallest node of the tree greater than n and the largest node smaller
>than n?

Use std::lower_boun d and std::upper_boun d (assuming that you have,
or write, suitable iterators for your tree.)

You should probably be using std::map or std::multimap in the first
place instead of trying to create your own. Review section 17.4 and
18.7 in Stroustrup _The C++ Programming Language_