[algogeeks] Finding closest double in a Btree

2012-02-20 Thread Supraja Jayakumar
Hi Question is given a binary tree and a key K, code to find the node with the closest value. I'd be happy to receive some feedback about my solution too. Pls find the code below: class FindingClosestNodeInTree { private static double difference = 0.0; private static doule key = 0.0; int

Re: [algogeeks] Finding closest double in a Btree

2012-02-20 Thread payal gupta
here is the soln. http://ideone.com/Qu0a0#view_edit_box however dere's a problem which needs to be resolved the prob is if the diff is 0 then due to the use of abs() its getting overriden i'm not able to find way out of it... ny suggestns are welcum.. Regards, PAYAL GUPTA. On Mon,

[algogeeks] Re: Finding closest double in a Btree

2012-02-20 Thread Don
Supraja, I think that your solution will work, but it does more work than is necessary. You don't need to traverse the entire tree. node findClosest(node root, double k) { node result = root; double diff = fabs(root-value - k); for(node loc = root; loc; loc = (loc-value k) ? loc-left :

Re: [algogeeks] Re: Finding closest double in a Btree

2012-02-20 Thread Supraja Jayakumar
Hi Don, Thanks for your feedback. Yea. makes sense to be comparing only right or left. Thanks All Supraja On Mon, Feb 20, 2012 at 9:44 AM, Don dondod...@gmail.com wrote: Supraja, I think that your solution will work, but it does more work than is necessary. You don't need to traverse the

[algogeeks] Re: Finding closest double in a Btree

2012-02-20 Thread Dave
@Don: Aren't you assuming a binary _search_ tree? Only a binary tree was specified by the OP. Dave On Feb 20, 10:44 am, Don dondod...@gmail.com wrote: Supraja, I think that your solution will work, but it does more work than is necessary. You don't need to traverse the entire tree. node

[algogeeks] Re: Finding closest double in a Btree

2012-02-20 Thread Don
I should have included reasoning with my code. If the current location is less than k, everything to the left will be further from k. Thus, you only need to look to the right. The opposite is true if the current location is greater than k. We're only interested in the left side. Thus there is

[algogeeks] Re: Finding closest double in a Btree

2012-02-20 Thread Don
Yes, I am assuming a binary search tree. The problem is trivial otherwise. If it is just a binary tree, you visit each node and keep track of the closest. Don On Feb 20, 5:02 pm, Dave dave_and_da...@juno.com wrote: @Don: Aren't you assuming a binary _search_ tree? Only a binary tree was

Re: [algogeeks] Re: Finding closest double in a Btree

2012-02-20 Thread Supraja Jayakumar
@Don hmm, this problem, though it seems simple, is a bit twisted. probably because of the double. Thanks for the explanation. Supraja On Mon, Feb 20, 2012 at 4:13 PM, Don dondod...@gmail.com wrote: Yes, I am assuming a binary search tree. The problem is trivial otherwise. If it is just a

[algogeeks] Re: Finding closest double in a Btree

2012-02-20 Thread Dave
@Don: By that measure, it also is trivial if the tree is a BST. You just find the largest node x and the smallest one x and choose between them. But since the original problem did not specify a BST, your solution is non-responsive. If I were grading a test, I'd have to count your solution as

[algogeeks] Re: Finding closest double in a Btree

2012-02-20 Thread Gene
Not to mention the subject line seems to be asking about B-Trees, which is no kind of binary tree, so the OP gets it wrong, too. On Feb 20, 7:28 pm, Dave dave_and_da...@juno.com wrote: @Don: By that measure, it also is trivial if the tree is a BST. You just find the largest node x and the

Re: [algogeeks] Re: Finding closest double in a Btree

2012-02-20 Thread saurabh singh
@gene probably you are saying this on the basis of the subject of the mail?Please read the problem statement stated in the mail.Even its a B tree doesn't effects the algorithm proposed by don which says *traverse each node and keep track of minimum.* So irrespective of the data structure used

[algogeeks] Re: Finding closest double in a Btree

2012-02-20 Thread Gene
Sure the algorithm works for any binary tree, but a B-Tree is a more general data structure. So the problem statement is confusing. This is probably the reason some people gave alternatives that only work with a BST. A BST is a special case of a B-Tree. On Feb 20, 8:58 pm, saurabh singh

[algogeeks] Re: Finding closest double in a Btree

2012-02-20 Thread Dave
@Gene: I don't know what is confusing about the OP's problem statement: Question is given a binary tree and a key K, code to find the node with the closest value. What do you find confusing about that? Are you opposed to using shorthand in the subject line that is then clarified in the body of

[algogeeks] Re: Finding closest double in a Btree

2012-02-20 Thread Gene
Just the topic line: Finding closest double in a Btree On Feb 20, 9:37 pm, Dave dave_and_da...@juno.com wrote: @Gene: I don't know what is confusing about the OP's problem statement: Question is given a binary tree and a key K, code to find the node with the closest value. What do you

[algogeeks] Re: Finding closest double in a Btree

2012-02-20 Thread Gene
The topic of the discussion is: Finding closest double in a Btree A binary tree that is also a B-Tree is (roughly) a Binary Search Tree. On Feb 20, 9:37 pm, Dave dave_and_da...@juno.com wrote: @Gene: I don't know what is confusing about the OP's problem statement: Question is given a

Re: [algogeeks] Re: Finding closest double in a Btree

2012-02-20 Thread Supraja Jayakumar
:) Apologize for the mistake - it is a BST. Thank You On Mon, Feb 20, 2012 at 7:46 PM, Gene gene.ress...@gmail.com wrote: The topic of the discussion is: Finding closest double in a Btree A binary tree that is also a B-Tree is (roughly) a Binary Search Tree. On Feb 20, 9:37 pm, Dave

Re: [algogeeks] Re: Finding closest double in a Btree

2012-02-20 Thread atul anand
@all : this little bit different question , but kinda related to it i am getting segmentation fault in one test case .. but not able to figure out why it is happening little help required. question is , given a BST find floor of a given key. inorder of BST = 10 20 30 40 50 key

Re: [algogeeks] Re: Finding closest double in a Btree

2012-02-20 Thread atul anand
@above : typo mistake : in the given example inorder of BST = 10 20 30 40 50 key = 27 output: floor= 20 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com.