QUESTION

Given a binary search tree and a target node K. The task is to find the node with minimum absolute difference with given target value K.\n\n\n\nExamples:\n\n// For binary search tree\nInput : k = 4\nOutput : 4\n\nInput : k = 18\nOutput : 17\n\nInput : k = 12\nOutput : 9.

ANSWER

// Recursive C++ program to find key closest to k
// in given Binary Search Tree.
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
 
/* A binary tree node has key, pointer to left child
and a pointer to right child */
struct Node
{
    int key;
    struct Node* left, *right;
};
 
/* Utility that allocates a new node with the
  given key and NULL left and right pointers. */
struct Node* newnode(int key)
{
    struct Node* node = new (struct Node);
    node->key = key;
    node->left = node->right  = NULL;
    return (node);
}
 
// Function to find node with minimum absolute
// difference with given K
// min_diff   --> minimum difference till now
// min_diff_key  --> node having minimum absolute
//                   difference with K
void maxDiffUtil(struct Node *ptr, int k, int &min_diff,
                                      int &min_diff_key)
{
    if (ptr == NULL)
        return ;
 
    // If k itself is present
    if (ptr->key == k)
    {
        min_diff_key = k;
        return;
    }
 
    // update min_diff and min_diff_key by checking
    // current node value
    if (min_diff > abs(ptr->key - k))
    {
        min_diff = abs(ptr->key - k);
        min_diff_key = ptr->key;
    }
 
    // if k is less than ptr->key then move in
    // left subtree else in right subtree
    if (k < ptr->key)
        maxDiffUtil(ptr->left, k, min_diff, min_diff_key);
    else
        maxDiffUtil(ptr->right, k, min_diff, min_diff_key);
}
 
// Wrapper over maxDiffUtil()
int maxDiff(Node *root, int k)
{
    // Initialize minimum difference
    int min_diff = INT_MAX, min_diff_key = -1;
 
    // Find value of min_diff_key (Closest key
    // in tree with k)
    maxDiffUtil(root, k, min_diff, min_diff_key);
 
    return min_diff_key;
}
 
// Driver program to run the case
int main()
{
    struct Node *root = newnode(9);
    root->left    = newnode(4);
    root->right   = newnode(17);
    root->left->left = newnode(3);
    root->left->right = newnode(6);
    root->left->right->left = newnode(5);
    root->left->right->right = newnode(7);
    root->right->right = newnode(22);
    root->right->right->left = newnode(20);
    int k = 18;
    cout << maxDiff(root, k);
    return 0;
}