# Binary search tree

Discussion in 'C++' started by sarajan82@gmail.com, Nov 25, 2007.

1. ### Guest

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

, Nov 25, 2007

2. ### Alf P. SteinbachGuest

* :
>
> 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

have been off-topic if it weren't homework.

The point of homework is to learn something by doing it yourself.

homework questions and so on: you should always read a group's FAQ
before posting.

Cheers, & hth.,

- Alf

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

Alf P. Steinbach, Nov 25, 2007

3. ### David HarmonGuest

On Sun, 25 Nov 2007 03:29:33 -0800 (PST) in comp.lang.c++,
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_bound and std::upper_bound (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_

David Harmon, Nov 25, 2007