I should have included reasoning with my code.
If the current location is less than k, everything to the left will be
further from k. Thus, you only need to look to the right.
The opposite is true if the current location is greater than k. We're
only interested in the left side.
Thus there is always a single path to follow, and recursion is not
required.
The iterative solution is O(depth of tree). On average, for a tree
with n elements, that is O(log n).
Don
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.
