Question

[Efficient algorithm to traverse tree in time O(k+1) question]

http://f.imgtmp.com/BMas4.jpg

How do I make an algorithm that's efficient like it asks? Also isn't the +1 irrelevant for the big O notation or am I missing something?

Answer 1

Like, could the notation be simplied to O(n)?

Answer 2

void printAtMost( key x, treeNode n )
{
if( n < x )
{
print n
if( n->left )
printAtMost( x, n->left );
if( n->right )
printAtMost( x, n->right );
}
return;
}