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 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 the posting?
>
> Dave
>
> On Feb 20, 8:19 pm, Gene <gene.ress...@gmail.com> wrote:
>
>
>
>
>
>
>
> > 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.
