I was fairly certain that the poster was asking about binary search trees. I realized that he did not say that, but I also realized that there is nothing to the problem if it is not a binary search tree. So I answered the problem which I believed the poster was asking. That might not fly in school, but in industry that is called anticipating the customer's needs. Don
On Feb 20, 6: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 -- 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.