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.
