find numbers in BST

[usgog]

Given a binary search tree, how to find two numbers that can add up to
a given number K?

 

[Christian]

Given a binary search tree, how to find two numbers that can add up to
a given number K?

nice homework .. have much fun with it..

 

[Daniel Pitts]

Given a binary search tree, how to find two numbers that can add up to
a given number K?

Its quite simple, start at both ends and work your way toward K/2, or
start at K/2, and work your way out.

 

[Andreas Leitgeb]

Its quite simple, start at both ends and work your way toward K/2, or
start at K/2, and work your way out.

I wonder, if a sorted double-linked list of the available numbers wouldn't
allow for a more efficient algorithm than a binary search tree.

 

[Roedy Green]

Given a binary search tree, how to find two numbers that can add up to
a given number K?

Here is a very primitive algorithm. Traverse the tree. For every
element, retraverse the tree looking for K-this.

Here is a more sophisticated algorithm:
You are looking for pairs of the form iand K-i.
So first traverse the tree and record in a java.util.BitSet which
numbers you find.

Now traverse the BitSet enumerating i looking at elements i and K-i.

see http://mindprod.com/jgloss/binary.html#BITSET

 

[Roedy Green]

Given a binary search tree, how to find two numbers that can add up to
a given number K?

here's another algorithm. Sort the elements. see
http://mindprod.com/jgloss/binarysearch.html