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.
