Binary search tree

[sarajan82]

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]

* (e-mail address 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

Please don't post homework, and please don't post homework that would
have been off-topic if it weren't homework.

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

See this group's FAQ for more information about topicality, posting
homework questions and so on: you should always read a group's FAQ
before posting.

Cheers, & hth.,

- Alf

 

[David Harmon]

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