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
    #1
    1. Advertising

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

    --
    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
    #2
    1. Advertising

  3. David Harmon Guest

    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
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,110
  2. sharan
    Replies:
    4
    Views:
    689
    CBFalconer
    Oct 30, 2007
  3. sharan
    Replies:
    2
    Views:
    830
    SM Ryan
    Oct 31, 2007
  4. sharan
    Replies:
    1
    Views:
    689
    CBFalconer
    Oct 30, 2007
  5. Bogdan

    Binary tree search vs Binary search

    Bogdan, Oct 18, 2010, in forum: C Programming
    Replies:
    22
    Views:
    3,067
    Michael Angelo Ravera
    Oct 21, 2010
Loading...

Share This Page