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 <saurab...@gmail.com> wrote: > @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 this solution is bound to > work.... > closest: > arguments: dataStructure T,int number > > tmp:=getelem(T); > min=tmp.value > while( getelem returns non null values) > do > nxt:=getelem(T); > > if(abs(nxt.value-number)<min) then > tmp=nxt > min=nxt.value > done > > done > > return tmp > > The nextelem function can be written according to the data structure used. > > Saurabh Singh > B.Tech (Computer Science) > MNNIT > blog:geekinessthecoolway.blogspot.com > > > > > > > > On Tue, Feb 21, 2012 at 6:06 AM, Gene <gene.ress...@gmail.com> wrote: > > 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 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 wrong, figuring that you do not know the difference > > > between a binary tree and a binary search tree. > > > > Dave > > > > On Feb 20, 5: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 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 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 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 : > > loc->right) > > > > > > > { > > > > > > double newDiff = fabs(loc->value - k); > > > > > > if (newDiff < diff) > > > > > > { > > > > > > result = loc; > > > > > > diff = newDiff; > > > > > > } > > > > > > } > > > > > > return result; > > > > > > > } > > > > > > > On Feb 20, 5:24 am, Supraja Jayakumar <suprajasank...@gmail.com> > > > > > > wrote: > > > > > > > > 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 main() { > > > > > > > BinaryTree bt; > > > > > > > bt.insert(20.43); > > > > > > > bt.insert(12.78); > > > > > > > bt.insert(19.89); > > > > > > > bt.insert(32.69); > > > > > > > bt.insert(2.54); > > > > > > > cout << "Please provide the key value" << endl; > > > > > > > cin >> key; > > > > > > > const Node &closestNode = closestValue(bt); > > > > > > > cout << << "Node that has the closest value to " << << > > > > > > > closestNode.value; > > > > > > > return 1;} > > > > > > > > const Node & closestValue(const BinaryTree &node) { > > > > > > > if(node==null) > > > > > > > return; > > > > > > > > int val = node.value; > > > > > > > int currDiff = val > key ? val-key:key-val; > > > > > > > difference = currDiff > difference ? currDiff:difference; > > > > > > > if(node.left!=null) > > > > > > > closestValue(node.left); > > > > > > > if(node.right!=null) > > > > > > > closestValue(node.right); > > > > > > > return difference; > > > > > > > > } > > > > > > > } > > > > > > > > Thanks > > > > > > > Supraja J- Hide quoted text - > > > > > > - Show quoted text - > > > -- > > 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. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. -- 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. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.