BST: remove less than

[Ridimz]

I have implemented a binary search tree and am interested in displaying all
keys less than a certain value. I understand how to approach this task if
the searchValue is equal to root.key(). Otherwise I'm lost. Any suggestions
or examples would be greatly appreciated

Thanks,
Ridimz

[Mike Wahler]

"Ridimz" <ri****@SPAMyahooFREE.com> wrote in message
news:dr******************@twister.southeast.rr.com ...

I have implemented a binary search tree and am interested in displaying all keys less than a certain value. I understand how to approach this task if
the searchValue is equal to root.key(). Otherwise I'm lost. Any suggestions or examples would be greatly appreciated
Without seeing any specific code or specific questions,
all I can say is that you can use the 'less than'
relational operator < to determine whether one value
is less than another.

if(x < y)
// value of 'x' is less than value of 'y'

-Mike

Thanks,
Ridimz

[Josh Sebastian]

On Sat, 04 Oct 2003 06:06:01 +0000, Ridimz wrote:

I have implemented a binary search tree and am interested in displaying all
keys less than a certain value. I understand how to approach this task if
the searchValue is equal to root.key(). Otherwise I'm lost. Any suggestions
or examples would be greatly appreciated

In a BST, all elements less than the current node's value are to
the left. So keep moving down and to the left until you find the first
node with a value less than you value, and display the values of all the
nodes on the subtree with that node for the root.

Josh

[Richard Heathfield]

Josh Sebastian wrote:

On Sat, 04 Oct 2003 06:06:01 +0000, Ridimz wrote:

I have implemented a binary search tree and am interested in displaying
all keys less than a certain value. I understand how to approach this
task if the searchValue is equal to root.key(). Otherwise I'm lost. Any
suggestions or examples would be greatly appreciated

In a BST, all elements less than the current node's value are to
the left. So keep moving down and to the left until you find the first
node with a value less than you value, and display the values of all the
nodes on the subtree with that node for the root.

(Please select a non-proportional font.)

Let's test that theory. I'm looking for anything less than H in the
following tree:

M
F R
D I P U
A E G J N Q T W

Your algorithm starts by going from M to F. F is less than H, so your
algorithm will display the values of all the nodes on the subtree with F at
the root. These are A, D, E, F, G, I, J.

Neither I nor J is < H. I conclude that the algorithm is flawed.

--
Richard Heathfield : bi****@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

[Ridimz]

"Ridimz" <ri****@SPAMyahooFREE.com> wrote...

Gentlemen,

Your suggestions successfully got me into the right frame of mind to solve
my proble.

Thank you!
Ridimz

[Stuart Golodetz]

"Ridimz" <ri****@SPAMyahooFREE.com> wrote in message
news:dr******************@twister.southeast.rr.com ...

I have implemented a binary search tree and am interested in displaying all keys less than a certain value. I understand how to approach this task if
the searchValue is equal to root.key(). Otherwise I'm lost. Any suggestions or examples would be greatly appreciated

Thanks,
Ridimz

void output_all_less_than(const T& t, std::ostream& os = std::cout, const
Node *pNode = NULL) const
{
if(!pNode)
{
if(!m_nodes.empty()) pNode = &m_nodes.front();
else return;
}
if(Pred()(t, pNode->m_data) || t == pNode->m_data)
{
if(pNode->m_pLeft) output_all_less_than(t, os, pNode->m_pLeft);
}
else
{
if(pNode->m_pLeft) output_all_less_than(t, os, pNode->m_pLeft);
os << pNode->m_data << ' ';
if(pNode->m_pRight) output_all_less_than(t, os, pNode->m_pRight);
}
}

HTH,

Stuart.

[Stuart Golodetz]

"Stuart Golodetz" <sg*******@dial.pipex.com> wrote in message
news:3f*********************@news.dial.pipex.com.. .

"Ridimz" <ri****@SPAMyahooFREE.com> wrote in message
news:dr******************@twister.southeast.rr.com ...

I have implemented a binary search tree and am interested in displaying all

keys less than a certain value. I understand how to approach this task if the searchValue is equal to root.key(). Otherwise I'm lost. Any

suggestions

or examples would be greatly appreciated

Thanks,
Ridimz

void output_all_less_than(const T& t, std::ostream& os = std::cout, const
Node *pNode = NULL) const
{
if(!pNode)
{
if(!m_nodes.empty()) pNode = &m_nodes.front();
else return;
}
if(Pred()(t, pNode->m_data) || t == pNode->m_data)
{
if(pNode->m_pLeft) output_all_less_than(t, os, pNode->m_pLeft);
}
else
{
if(pNode->m_pLeft) output_all_less_than(t, os, pNode->m_pLeft);

Sorry, the above line could be more efficient:
if(pNode->m_pLeft) output(os, pNode->m_pLeft); // code for
output(std::ostream&, const Node*) const not posted (but trivial to
implement)

Cheers,

Stuart.
os << pNode->m_data << ' ';
if(pNode->m_pRight) output_all_less_than(t, os, pNode->m_pRight);
}
}

HTH,

Stuart.

[Josh Sebastian]

On Sat, 04 Oct 2003 16:55:55 +0000, Richard Heathfield wrote:

I conclude that the algorithm is flawed.

Umm... I left it as an exercise for the reader? Thanks Richard. OTOH, it's
pretty easy to go from my "algorithm" to the correct answer.

Josh