 |
 | Home | Contact Us | FAQ | Search & Site Map | Link to Us |
 | Sign In | Join | Other 45 Sites in Network |
Java Forum / General / December 2007find numbers in BST
Given a binary search tree, how to find two numbers that can add up to a given number K? usgog@yahoo.com schrieb: > 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.. > 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.  SignatureDaniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/> >> 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. 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. On Wed, 5 Dec 2007 09:45:41 -0800 (PST), "usgog@yahoo.com" <usgog@yahoo.com> wrote, quoted or indirectly quoted someone who said >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 SignatureRoedy Green Canadian Mind Products The Java Glossary http://mindprod.com On Wed, 5 Dec 2007 09:45:41 -0800 (PST), "usgog@yahoo.com" <usgog@yahoo.com> wrote, quoted or indirectly quoted someone who said >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 SignatureRoedy Green Canadian Mind Products The Java Glossary http://mindprod.com Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
Reply to this Message
|
 Sign In
 Join
 My Latest Posts My Monitored Threads My Blog My Photo Gallery My Profile My Homepage Start New Thread Enable EMail Alerts Rate this Thread
|
©2008 Advenet LLC Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.