Find the closest element in Binary Search Tree

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;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro