Question

Given a binary search tree and a value k, implement a function to find the node in the binary search tree whose value is closest to k.

Write the program in Java

Syntax: int lookup(Node node)

Answer 1

// class to store a value

class Val{

int value;

}

// Function to find node with minimum absolute

// difference with given K

// min_diff -. minimum difference till now

// min_diff_data -. node having minimum absolute

// difference with K

void lookupUtil(Node node, int k, Val min_diff,

Val min_diff_data)

{

if (node == NULL)

return ;

// If k itself is present

if (node.data == k)

{

min_diff_data.value = k;

return;

}

// update min_diff and min_diff_data by checking

// current node value

if (min_diff.value > Math.abs(node.data - k))

{

min_diff.value = Math.abs(node.data - k);

min_diff_data.value = node.data;

}

// if k is less than node.data then move in

// left subtree else in right subtree

if (k < node.data)

lookupUtil(node.left, k, min_diff, min_diff_data);

else

lookupUtil(node.right, k, min_diff, min_diff_data);

}

int lookup(Node root, int k)

{

// Initialize minimum difference

Val min_diff = new Val();

min_diff.value = Integer.INT_MAX

Val min_diff_data = new Val();

min_diff_data.value = -1;

// Find value of min_diff_data (Closest data

// in tree with k)

maxDiffUtil(root, k, min_diff, min_diff_data);

return min_diff_data.value;

}