Velocity Reviews > C++ > Binary search tree

# Binary search tree

sarajan82@gmail.com
Guest
Posts: n/a

 11-25-2007
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

Alf P. Steinbach
Guest
Posts: n/a

 11-25-2007
* http://www.velocityreviews.com/forums/(E-Mail Removed):
>
> 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?

David Harmon
Guest
Posts: n/a

 11-25-2007
On Sun, 25 Nov 2007 03:29:33 -0800 (PST) in comp.lang.c++,
(E-Mail Removed) 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_