@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.
