Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
n: node
d: difference between node to be checked and key targetted
un = ultimate node or solution node
CK(n, d)
if(abs(d) < min)
un = n
if(d == 0)
return
if(d <0)
CK(n->r, n->r - k)
else
CK(n->l, n->l - k)
I wonder what value would you use for argument "d" in the initial call for the root. Also I don't think we can assume both children will always be present. Just minor details though.
Usually I wouldn't compare doubles using ==, but I am just too lazy to write a macro to compare against epsilon.
const Node* closest (const Node* node, double value,
const Node* parent = NULL) {
if (NULL == node) {
return NULL;
}
const Node *left = NULL, *right = NULL, *result = node;
if ((NULL == parent && value < node->data) ||
(value < parent->data && value < node->data) {
left = closest(node->left, value, node);
}
if ((NULL == parent && value > node->data) ||
(value > parent->data && value > node->data) {
right = closest(node->right, value, node);
}
if (NULL != left &&
std::abs(left->data - value) < std::abs(node->data - value)) {
result = left;
}
if (NULL != right &&
std::abs(right->data - value) < std::abs(result->data - value)) {
result = right;
}
return result;
}
Another one (recursive):
public static BTNode closest(BTNode node, double k) {
if (node == null) {
return null;
}
BTNode nl = closest(node.left, k);
BTNode nr = closest(node.right, k);
if (nl != null) {
BTNode temp = Math.min(Math.abs(node.data - k), Math.abs(nl.data - k)) == Math.abs(node.data - k) ? node : nl;
if (nr != null) {
return Math.min(Math.abs(temp.data - k), Math.abs(nr.data - k)) == Math.abs(temp.data - k) ? temp : nr;
}
return temp;
}
if (nr != null) {
return Math.min(Math.abs(node.data - k), Math.abs(nr.data - k)) == Math.abs(node.data - k) ? node : nr;
}
return node;
}
A recursive solution which returns the root if it is closer to the given number, or the closest node in the right/left subtree if that is closer than the root:
Node* closest_node(Node* root, int K)
{
if((double)K>root->data)
{
if(root->right==NULL)
return root;
else
{
Node* closest_in_subtree = closest_node(root->right,K);
return abs((double)K-root->data)<abs(double(K)-closest_in_subtree->data) ? root : closest_in_subtree;
}
}
else
{
if(root->left==NULL)
return root;
else
{
Node* closest_in_subtree = closest_node(root->left,K);
return abs(double(K)-root->data)<abs(double(K)-closest_in_subtree->data) ? root : closest_in_subtree;
}
}
}
Running time would be O(log n) if the tree is balanced.
Hi
I would be happy to get some feedback on this code.
class Finding ClosestNodeInTree {
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;
// Some kind of traversal - A Breadth First Search might be useful.
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;
}
}
I know I am not doing BST. But sometimes the value might be "closer" to either the left side of the value or the right side of the value (thinking on a number line) regardless of whether is lesser or greater than the parent value right ? Or am I missing something ?
Please send in your comments.
Thank You
Logic: Find closest value in the left or right child and compare it with current node.
double find(Node * root, double val){
double delta = val - root->data;
double x;
if(delta > 0 ) // look in right
x = find(rott->right,val);
else
x = find(root->left,val);
double deltax = abs(x-val);
if(deltax < abs(delta))
return x;
else
return root->data;
}
del_min <- INFINITY
p <- root
p_min <- root
while (p)
del_p = (p->val - K)
p_min_dash = p, del_min_dash = del_p
if (p->left)
del_l = (p->left->val - K)
if (abs(del_l) < abs(del_p))
del_min_dash = abs(del_l)
p_min_dash = p->left
if (p->right)
del_r = (p->right->val - K)
if (abs(del_r) < abs(del_p))
del_min_dash = abs(del_r)
p_min_dash = p->right
if (del_min_dash < del_min)
del_min = del_min_dash
p_min = p_min_dash
//Traverse
if (p_min_dash == p)
if ((p->left) && ((del_p XOR del_l < 0))
p = p->left
if ((p->right) && ((del_p XOR del_r < 0))
p = p->right
else
if (p_min_dash == p->left)
p = p->left
else
p = p->right
end
end
end //end p
del_min <- INFINITY
p <- root
p_min <- root
while (p)
del_p = (p->val - K)
p_min_dash = p, del_min_dash = del_p
if (p->left)
del_l = (p->left->val - K)
if (abs(del_l) < abs(del_p))
del_min_dash = abs(del_l)
p_min_dash = p->left
if (p->right)
del_r = (p->right->val - K)
if (abs(del_r) < abs(del_p))
del_min_dash = abs(del_r)
p_min_dash = p->right
if (del_min_dash < del_min)
del_min = del_min_dash
p_min = p_min_dash
//Traverse
if (p_min_dash == p)
if ((p->left) && ((del_p XOR del_l < 0))
p = p->left
if ((p->right) && ((del_p XOR del_r < 0))
p = p->right
else
if (p_min_dash == p->left)
p = p->left
else
p = p->right
end
end
end //end p
del_min <- INFINITY
p <- root
p_min <- root
while (p)
del_p = (p->val - K)
p_min_dash = p, del_min_dash = del_p
if (p->left)
del_l = (p->left->val - K)
if (abs(del_l) < abs(del_p))
del_min_dash = abs(del_l)
p_min_dash = p->left
if (p->right)
del_r = (p->right->val - K)
if (abs(del_r) < abs(del_p))
del_min_dash = abs(del_r)
p_min_dash = p->right
if (del_min_dash < del_min)
del_min = del_min_dash
p_min = p_min_dash
//Traverse
if (p_min_dash == p)
if ((p->left) && ((del_p XOR del_l < 0))
p = p->left
if ((p->right) && ((del_p XOR del_r < 0))
p = p->right
else
if (p_min_dash == p->left)
p = p->left
else
p = p->right
end
end
end //end p
//BC not checked properly
del_min <- INFINITY
p <- root
p_min <- root
while (p)
del_p = (p->val - K)
p_min_dash = p, del_min_dash = del_p
//Tackle left
if (p->left)
del_l = (p->left->val - K)
if (abs(del_l) < abs(del_p))
del_min_dash = abs(del_l)
p_min_dash = p->left
//Tackle right
if (p->right)
del_r = (p->right->val - K)
if (abs(del_r) < abs(del_p))
del_min_dash = abs(del_r)
p_min_dash = p->right
// Tackle root, left, right
if (del_min_dash < del_min)
del_min = del_min_dash
p_min = p_min_dash
//Traverse
if (p_min_dash == p)
if ((p->left) && ((del_p XOR del_l < 0))
p = p->left
if ((p->right) && ((del_p XOR del_r < 0))
p = p->right
else
if (p_min_dash == p->left)
p = p->left
else
p = p->right
end
end
end //end p
//BC not checked properly
del_min <- INFINITY
p <- root
p_min <- root
while (p)
del_p = (p->val - K)
p_min_dash = p, del_min_dash = del_p
//Tackle left
if (p->left)
del_l = (p->left->val - K)
if (abs(del_l) < abs(del_p))
del_min_dash = abs(del_l)
p_min_dash = p->left
//Tackle right
if (p->right)
del_r = (p->right->val - K)
if (abs(del_r) < abs(del_p))
del_min_dash = abs(del_r)
p_min_dash = p->right
// Tackle root, left, right
if (del_min_dash < del_min)
del_min = del_min_dash
p_min = p_min_dash
//Traverse
if (p_min_dash == p)
if ((p->left) && ((del_p XOR del_l < 0))
p = p->left
if ((p->right) && ((del_p XOR del_r < 0))
p = p->right
else
if (p_min_dash == p->left)
p = p->left
else
p = p->right
end
end
end //end p
public int findNearest(double key) {
Node previousNode = null;
Node traverseNode = root;
int absValue;
float value;
while (traverseNode != null) {
if (key < traverseNode.getValue()) {
previousNode = traverseNode;
traverseNode = traverseNode.getLeft();
} else {
previousNode = traverseNode;
traverseNode = traverseNode.getRight();
}
if ((traverseNode == null)
|| (key > previousNode.getValue() && key < traverseNode
.getValue())) {
break;
}
}
Double diffParent = Math.abs(previousNode.getValue()- key);
Double diffNode = Math.abs(traverseNode.getValue()- key);
if(diffParent <diffNode){
return previousNode.getValue();
}else
{
return traverseNode.getValue();
}
}
public int findNearest(double key) {
Node previousNode = null;
Node traverseNode = root;
int absValue;
float value;
while (traverseNode != null) {
if (key < traverseNode.getValue()) {
previousNode = traverseNode;
traverseNode = traverseNode.getLeft();
} else {
previousNode = traverseNode;
traverseNode = traverseNode.getRight();
}
if ((traverseNode == null)
|| (key > previousNode.getValue() && key < traverseNode
.getValue())) {
break;
}
}
Double diffParent = Math.abs(previousNode.getValue()- key);
Double diffNode = Math.abs(traverseNode.getValue()- key);
if(diffParent <diffNode){
return previousNode.getValue();
}else
{
return traverseNode.getValue();
}
}
Usually I wouldn't compare doubles using ==, but I am just too lazy to write a macro to compare against epsilon.
const Node* closest (const Node* node, double value, const Node* parent = NULL) {
if (NULL == node) {
return NULL;
}
const Node *left = NULL, *right = NULL, *result = node;
if ((NULL == parent && value < node->data) || (value < parent->data && value < node->data) {
left = closest(node->left, value, node);
}
if ((NULL == parent && value > node->data) || (value > parent->data && value > node->data) {
right = closest(node->right, value, node);
}
if (NULL != left && std::abs(left->data - value) < std::abs(node->data - value)) {
result = left;
}
if (NULL != right && std::abs(right->data - value) < std::abs(result->data - value)) {
result = right;
}
return result;
}
Usually I wouldn't compare doubles using ==, but I am just too lazy to write a macro to compare against epsilon.
const Node* closest (const Node* node, double value, const Node* parent = NULL) {
if (NULL == node) {
return NULL;
}
const Node *left = NULL, *right = NULL, *result = node;
if ((NULL == parent && value < node->data) || (value < parent->data && value < node->data) {
left = closest(node->left, value, node);
}
if ((NULL == parent && value > node->data) || (value > parent->data && value > node->data) {
right = closest(node->right, value, node);
}
if (NULL != left && std::abs(left->data - value) < std::abs(node->data - value)) {
result = left;
}
if (NULL != right && std::abs(right->data - value) < std::abs(result->data - value)) {
result = right;
}
return result;
}
//example call: findClosest(t, 4.1, MAX_DOUBLE);
double findClosest(Node t, double value, double closestSofar)
{
if(delta(value, t.value) < delta(value, closestSofar))
{
closestSofar = t.value;
}
if(t.value < value)
{
closestSofar = findClosest(t.right, value, closestSofar);
}
else
{
closestSofar = findClosest(t.left, value, closestSofar);
}
return closestSofar;
}
private double delta(double value, double value2) {
double d = value - value2;
if(d < 0)
return -1*d;
return d;
}
import java.util.Arrays;
class TreeNode
{
public double value;
public TreeNode left,right;
public TreeNode(double v)
{
value = v;
}
}
class BST
{
TreeNode root = null;
public void insert(double x)
{
if( root == null )
{
root = new TreeNode(x);
return;
}
TreeNode current = root;
TreeNode parent = root;
while(current!=null)
{
parent = current;
if( current.value > x )
{
current = current.left;
}else
{
current = current.right;
}
}
if( parent.value > x )
{
parent.left = new TreeNode(x);
}else
{
parent.right = new TreeNode(x);
}
}
public double findCloset(double [] array, int key)
{
for(double x : array)
{
insert(x);
}
//tree built
TreeNode t = root;
while(t!=null)
{
double x = t.value;
if( x > key )
{
if(t.left != null && Math.abs(t.left.value - key) < Math.abs(x - key))
{
t = t.left;
}else
{
return t.value;
}
}else
{
if(t.right != null && Math.abs(t.right.value - key) < Math.abs(x - key))
{
t = t.right;
}else
{
return t.value;
}
}
}
return 0;
}
}
public class findArray
{
public static void main(String[] arg)
{
BST b = new BST();
double []v = {1.2,3.4,5.6,1,4.5,6.7,3.2,2.9,3.1};
System.out.println(b.findCloset(v, 3));
}
}
import java.util.Arrays;
class TreeNode
{
public double value;
public TreeNode left,right;
public TreeNode(double v)
{
value = v;
}
}
class BST
{
TreeNode root = null;
public void insert(double x)
{
if( root == null )
{
root = new TreeNode(x);
return;
}
TreeNode current = root;
TreeNode parent = root;
while(current!=null)
{
parent = current;
if( current.value > x )
{
current = current.left;
}else
{
current = current.right;
}
}
if( parent.value > x )
{
parent.left = new TreeNode(x);
}else
{
parent.right = new TreeNode(x);
}
}
public double findCloset(double [] array, int key)
{
for(double x : array)
{
insert(x);
}
//tree built
TreeNode t = root;
while(t!=null)
{
double x = t.value;
if( x > key )
{
if(t.left != null && Math.abs(t.left.value - key) < Math.abs(x - key))
{
t = t.left;
}else
{
return t.value;
}
}else
{
if(t.right != null && Math.abs(t.right.value - key) < Math.abs(x - key))
{
t = t.right;
}else
{
return t.value;
}
}
}
return 0;
}
}
public class findArray
{
public static void main(String[] arg)
{
BST b = new BST();
double []v = {1.2,3.4,5.6,1,4.5,6.7,3.2,2.9,3.1};
System.out.println(b.findCloset(v, 3));
}
}
import java.util.Arrays;
class TreeNode
{
public double value;
public TreeNode left,right;
public TreeNode(double v)
{
value = v;
}
}
class BST
{
TreeNode root = null;
public void insert(double x)
{
if( root == null )
{
root = new TreeNode(x);
return;
}
TreeNode current = root;
TreeNode parent = root;
while(current!=null)
{
parent = current;
if( current.value > x )
{
current = current.left;
}else
{
current = current.right;
}
}
if( parent.value > x )
{
parent.left = new TreeNode(x);
}else
{
parent.right = new TreeNode(x);
}
}
public double findCloset(double [] array, int key)
{
for(double x : array)
{
insert(x);
}
//tree built
TreeNode t = root;
while(t!=null)
{
double x = t.value;
if( x > key )
{
if(t.left != null && Math.abs(t.left.value - key) < Math.abs(x - key))
{
t = t.left;
}else
{
return t.value;
}
}else
{
if(t.right != null && Math.abs(t.right.value - key) < Math.abs(x - key))
{
t = t.right;
}else
{
return t.value;
}
}
}
return 0;
}
}
public class findArray
{
public static void main(String[] arg)
{
BST b = new BST();
double []v = {1.2,3.4,5.6,1,4.5,6.7,3.2,2.9,3.1};
System.out.println(b.findCloset(v, 3));
}
}
Algo:
Find left closest and right closest node of the given node in tree by traversing the tree.
At end return whichever of right and left is closer to the node
public Node find_closest(Node root, Node nodeToFound, Node left, Node right) {
if(root == NULL){
if(left != NULL && right != NULL){
if(abs(nodeToFound, left) < abs(nodeToFound, right)){
return left;
} else {
return right;
}
}
if(left == NULL){
return right;
}
return left;
}
if(nodeToFound.compare(root) < 0){
return find_closest(root->left, nodeToFound, left, root);
} else {
return find_closest(root->right, nodeToFound, root, right);
}
}
I think the key here is how to compare two double values. In java, can use BigDecimal but need to convert double to String first. My code is shown as follows:
public static Node closest(Node root, BigDecimal key){
if (root == null)
return null;
BigDecimal value = new BigDecimal(root.value+"");
int compare = key.compareTo(value);
if ( compare == 0){
return root;
}
else if (compare < 0){
if (root.left == null) return root;
else {
BigDecimal leftvalue = new BigDecimal(root.left.value + "");
if (key.compareTo(leftvalue) > 0){
if ((key.subtract(leftvalue)).compareTo(value.subtract(key)) <= 0)
return root.left;
else
return root;
}
else
return closest(root.left, key);
}
}
else if (compare > 0){
if (root.right == null) return root;
else{
BigDecimal rightvalue = new BigDecimal(root.right.value + "");
if (key.compareTo(rightvalue) < 0){
if ((key.subtract(value)).compareTo(rightvalue.subtract(key)) <= 0)
return root;
else
return root.right;
}
else
return closest(root.right, key);
}
}
return null;
}
class Node
{
Node* left;
Node* right;
double value;
}
doulbe findClosest (Node * root; double key)
{
vector<double> pathï¼›
while (root!=NULL)
{
if(root->value == key)
{return root-> value;}
else if(root->value > key)
{
path.push_back(root -> value);
root = root->left;
continue;
}
else
{
path.push_back(root->value);
root = root -> right;
continue;
}
}
path.push_back(key);
sort(path.begin(), path.end());
int len = path.size();
for (int i = 0; i<len; i++)
{
if (path[i] == key)
{
if (abs(path[i-1]-path[i]) < abs(path[i+1]-path[i]))
return path[i-1];
else
return path[i+1];
}
}
}
MinNode(node):
while (node.left):
node = node.left
return node
MaxNode(node):
while(node.right):
node = node.right
return node
Successor(node):
if (node.right):
return MinNode(node.right)
while (node.parent && node == node.parent.right):
node = node.parent
return node
Predecessor(node):
if node.left:
return MaxNode(node.left)
while (node.parent && node == node.left)
node = node.parent
return node
FindClosest (key):
node = Find(key)
s = Successor(node)
p = Predecessor(node)
if (Abs(s.key - key) < Abs(p.key - key)):
return s
else:
return p
#include <iostream>
#include <cmath>
using namespace std;
struct Node
{
Node *left;
Node *right;
double val;
Node():left(NULL), right(NULL){}
};
Node *find(Node *node, double key)
{
if (node == NULL)
return NULL;
double val = node->val;
if (val == key)
return node;
else if (val < key)
{
Node *ret = find(node->right, key);
if (ret == NULL)
return node;
else
return abs(node->val - key) < abs(ret->val - key) ? node : ret;
}
else
{
Node *ret = find(node->left, key);
if (ret == NULL)
return node;
else
return abs(node->val - key) < abs(ret->val - key) ? node : ret;
}
}
int main()
{
Node node[10];
for(int i = 0; i < 10; i++)
node[i].val = i;
node[4].left = &node[2];
node[4].right = &node[7];
node[2].left = &node[1];
node[2].right = &node[3];
node[1].left = &node[0];
node[7].left = &node[6];
node[7].right = &node[8];
node[6].left = &node[5];
node[8].right = &node[9];
Node *ret = find(&node[4], 4);
cout << "key:" << 4 << " ret:" << ret->val << endl;
ret = find(&node[4], 4.4);
cout << "key:" << 4.4 << " ret:" << ret->val << endl;
ret = find(&node[4], 10);
cout << "key:" << 10 << " ret:" << ret->val << endl;
ret = find(&node[4], 1.1);
cout << "key:" << 1.1 << " ret:" << ret->val << endl;
ret = find(&node[4], -1);
cout << "key:" << -1 << " ret:" << ret->val << endl;
ret = find(&node[3], 3.3);
cout << "key:" << 3.3 << " ret:" << ret->val << endl;
}
#include<iostream>
#include<vector>
#include<algorithm>
#include<cfloat>
struct node {
float value;
struct node *left;
struct node* right;
};
typedef struct node NODE;
NODE* constructBST(const std::vector<float>& numbers, int low, int high) {
if (low > high) {
return NULL;
}
int mid = (low + high) / 2;
NODE *root = new NODE;
root->value = numbers[mid];
root->left = constructBST(numbers, low, mid -1);
root->right = constructBST(numbers, mid+1, high);
return root;
}
float findClosest(NODE *root, float k) {
static float mindiff = FLT_MAX;
static float closest = 0.0F;
if (root == NULL)
return 0.0F;
if (fabs(root->value -k) < mindiff) {
mindiff = fabs(root->value-k);
closest = root->value;
}
findClosest(root->left, k);
findClosest(root->right, k);
return closest;
}
int main() {
// Read k
std::cout << "Enter key\n";
float k;
std::cin >> k;
// Read input numbers to a vector
std::cout << "Enter numbers\n";
std::vector<float> numbers;
float input;
while (std::cin >> input) {
numbers.push_back(input);
}
// Sort the vector
std::sort(numbers.begin(), numbers.end());
// Cosntruct a BST
NODE* root = constructBST(numbers, 0, numbers.size()-1);
// findClosest
float closestValue = findClosest(root, k);
std::cout << "Closest value is " << closestValue << std::endl;
return 0;
}
#include<iostream>
#include<vector>
#include<algorithm>
#include<cfloat>
struct node {
float value;
struct node *left;
struct node* right;
};
typedef struct node NODE;
NODE* constructBST(const std::vector<float>& numbers, int low, int high) {
if (low > high) {
return NULL;
}
int mid = (low + high) / 2;
NODE *root = new NODE;
root->value = numbers[mid];
root->left = constructBST(numbers, low, mid -1);
root->right = constructBST(numbers, mid+1, high);
return root;
}
float findClosest(NODE *root, float k) {
static float mindiff = FLT_MAX;
static float closest = 0.0F;
if (root == NULL)
return 0.0F;
if (fabs(root->value -k) < mindiff) {
mindiff = fabs(root->value-k);
closest = root->value;
}
findClosest(root->left, k);
findClosest(root->right, k);
return closest;
}
int main() {
// Read k
std::cout << "Enter key\n";
float k;
std::cin >> k;
// Read input numbers to a vector
std::cout << "Enter numbers\n";
std::vector<float> numbers;
float input;
while (std::cin >> input) {
numbers.push_back(input);
}
// Sort the vector
std::sort(numbers.begin(), numbers.end());
// Cosntruct a BST
NODE* root = constructBST(numbers, 0, numbers.size()-1);
// findClosest
float closestValue = findClosest(root, k);
std::cout << "Closest value is " << closestValue << std::endl;
return 0;
}
1. Keep two variables currDiff = Integer.MAX_VALUE and prevDiff = Integer.MAX_VALUE
2. Do BST,
but at each node do currDiff = node.value - key
if(Math.abs(currDiff) < prevDiff)
{
prevDiff = Math.abs(currDiff);
closest = node.value;
}
At the end return closest;
If the value is zero it is going to find that element, if not the closest one.
Here is the code for the algorithm I discussed:-
private static BTNode closestLookup(BTNode node, double data)
{
double currDiff = Integer.MAX_VALUE, prevDiff = Integer.MAX_VALUE;
BTNode closest = null;
while(node != null)
{
currDiff = node.data - data;
if(Math.abs(currDiff) < prevDiff)
{
prevDiff = Math.abs(currDiff);
closest = node;
}
if(node.data == data)
{
break;
}
else
{
if(data < node.data)
{
node = node.left;
}
else
{
node = node.right;
}
}
}
return closest;
}
A simple optimization on the code given here.
The loop can discontinue when the prevDiff is less than the current Diff. The node.data = data, < data or > data checks are needed only if currDiff < prevDiff
1) Naive solution is to store every element into an array, then scan whole element to find the closest element. Because Binary Tree can be converted as sorted array, this way is possible. However, it needs O(n) memory space and O(n) time complexity.
2) The better way is to follow tree nodes. The important point is that we should follow nodes until we find the leaf node unless the same value is found. Here is an example tree which I used.
3
2 100
1.9 2.8 3.1
Suppose input is (3.12), the closest value is 3.1. My idea is similar to Dev's idea. Just follow nodes using input value and store the value which has the smallest delta.
** ramya987 mentioned it is possible to optimize using curDiff < prevDiff. For my input 3.12, curDiff is much bigger than prevDiff when curNode is on 100(3-3.12 = -0.12, 100-3.12= 96.88). If we discontinue following nodes, it will return 3 as the closest node, but it is incorrect. 3.1 is the closest node. Thus, please follow nodes until the leaf node.
public double findCloset(TreeNode root, double key)
{
TreeNode t = root;
double closest = t.value;
while (t != null)
{
if(t.value == key)
{
//If it is exactly equal, comparison doens't need anymore
closest = t.value;
break;
}
else if (t.value > key)
{
t = t.left;
}
else
{
t = t.right;
}
if (t != null && Math.abs(t.value - key) < Math.abs(closest - key))
{
closest = t.value;
}
}
return closest;
}
Hi
I would be happy to get some feedback on this code.
class Finding ClosestNodeInTree {
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;
// Some kind of traversal - A Breadth First Search might be useful.
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;
}
}
I know I am not doing BST. But sometimes the value might be "closer" to either the left side of the value or the right side of the value (thinking on a number line) regardless of whether is lesser or greater than the parent value right ? Or am I missing something ?
Please send in your comments.
Thank You
If you already know the node's value is greater than the target value, then you shouldn't need to check the right subtree at all because they all will be farther from the target value than the node. Similarly for the opposite case.
This is true because the question says it's a binary search tree. If it were just a binary tree, then of course you have to check both subtrees as well.
Hi
I would be happy to get some feedback on this code.
class Finding ClosestNodeInTree {
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;
// Some kind of traversal - A Breadth First Search might be useful.
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;
}
}
I know I am not doing BST. But sometimes the value might be "closer" to either the left side of the value or the right side of the value (thinking on a number line) regardless of whether is lesser or greater than the parent value right ? Or am I missing something ?
Please send in your comments.
Thank You
Hi
I would be happy to get some feedback on this code.
class Finding ClosestNodeInTree {
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;
// Some kind of traversal - A Breadth First Search might be useful.
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;
}
}
I know I am not doing BST. But sometimes the value might be "closer" to either the left side of the value or the right side of the value (thinking on a number line) regardless of whether is lesser or greater than the parent value right ? Or am I missing something ?
Please send in your comments.
Thank You
Hi
I would be happy to get some feedback on this code.
class Finding ClosestNodeInTree {
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;
// Some kind of traversal - A Breadth First Search might be useful.
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;
}
}
I know I am not doing BST. But sometimes the value might be "closer" to either the left side of the value or the right side of the value (thinking on a number line) regardless of whether is lesser or greater than the parent value right ? Or am I missing something ?
Please send in your comments.
Thank You
Hi
I would be happy to get some feedback on this code.
class Finding ClosestNodeInTree {
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;
// Some kind of traversal - A Breadth First Search might be useful.
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;
}
}
I know I am not doing BST. But sometimes the value might be "closer" to either the left side of the value or the right side of the value (thinking on a number line) regardless of whether is lesser or greater than the parent value right ? Or am I missing something ?
Please send in your comments.
Thank You
import java.util.Arrays;
class TreeNode
{
public double value;
public TreeNode left,right;
public TreeNode(double v)
{
value = v;
}
}
class BST
{
TreeNode root = null;
public void insert(double x)
{
if( root == null )
{
root = new TreeNode(x);
return;
}
TreeNode current = root;
TreeNode parent = root;
while(current!=null)
{
parent = current;
if( current.value > x )
{
current = current.left;
}else
{
current = current.right;
}
}
if( parent.value > x )
{
parent.left = new TreeNode(x);
}else
{
parent.right = new TreeNode(x);
}
}
public double findCloset(double [] array, int key)
{
for(double x : array)
{
insert(x);
}
//tree built
TreeNode t = root;
while(t!=null)
{
double x = t.value;
if( x > key )
{
if(t.left != null && Math.abs(t.left.value - key) < Math.abs(x - key))
{
t = t.left;
}else
{
return t.value;
}
}else
{
if(t.right != null && Math.abs(t.right.value - key) < Math.abs(x - key))
{
t = t.right;
}else
{
return t.value;
}
}
}
return 0;
}
}
public class findArray
{
public static void main(String[] arg)
{
BST b = new BST();
double []v = {1.2,3.4,5.6,1,4.5,6.7,3.2,2.9,3.1};
System.out.println(b.findCloset(v, 3));
}
}
import java.util.Arrays;
class TreeNode
{
public double value;
public TreeNode left,right;
public TreeNode(double v)
{
value = v;
}
}
class BST
{
TreeNode root = null;
public void insert(double x)
{
if( root == null )
{
root = new TreeNode(x);
return;
}
TreeNode current = root;
TreeNode parent = root;
while(current!=null)
{
parent = current;
if( current.value > x )
{
current = current.left;
}else
{
current = current.right;
}
}
if( parent.value > x )
{
parent.left = new TreeNode(x);
}else
{
parent.right = new TreeNode(x);
}
}
public double findCloset(double [] array, int key)
{
for(double x : array)
{
insert(x);
}
//tree built
TreeNode t = root;
while(t!=null)
{
double x = t.value;
if( x > key )
{
if(t.left != null && Math.abs(t.left.value - key) < Math.abs(x - key))
{
t = t.left;
}else
{
return t.value;
}
}else
{
if(t.right != null && Math.abs(t.right.value - key) < Math.abs(x - key))
{
t = t.right;
}else
{
return t.value;
}
}
}
return 0;
}
}
public class findArray
{
public static void main(String[] arg)
{
BST b = new BST();
double []v = {1.2,3.4,5.6,1,4.5,6.7,3.2,2.9,3.1};
System.out.println(b.findCloset(v, 3));
}
}
import java.util.Arrays;
class TreeNode
{
public double value;
public TreeNode left,right;
public TreeNode(double v)
{
value = v;
}
}
class BST
{
TreeNode root = null;
public void insert(double x)
{
if( root == null )
{
root = new TreeNode(x);
return;
}
TreeNode current = root;
TreeNode parent = root;
while(current!=null)
{
parent = current;
if( current.value > x )
{
current = current.left;
}else
{
current = current.right;
}
}
if( parent.value > x )
{
parent.left = new TreeNode(x);
}else
{
parent.right = new TreeNode(x);
}
}
public double findCloset(double [] array, int key)
{
for(double x : array)
{
insert(x);
}
//tree built
TreeNode t = root;
while(t!=null)
{
double x = t.value;
if( x > key )
{
if(t.left != null && Math.abs(t.left.value - key) < Math.abs(x - key))
{
t = t.left;
}else
{
return t.value;
}
}else
{
if(t.right != null && Math.abs(t.right.value - key) < Math.abs(x - key))
{
t = t.right;
}else
{
return t.value;
}
}
}
return 0;
}
}
public class findArray
{
public static void main(String[] arg)
{
BST b = new BST();
double []v = {1.2,3.4,5.6,1,4.5,6.7,3.2,2.9,3.1};
System.out.println(b.findCloset(v, 3));
}
}
import java.util.Arrays;
class TreeNode
{
public double value;
public TreeNode left,right;
public TreeNode(double v)
{
value = v;
}
}
class BST
{
TreeNode root = null;
public void insert(double x)
{
if( root == null )
{
root = new TreeNode(x);
return;
}
TreeNode current = root;
TreeNode parent = root;
while(current!=null)
{
parent = current;
if( current.value > x )
{
current = current.left;
}else
{
current = current.right;
}
}
if( parent.value > x )
{
parent.left = new TreeNode(x);
}else
{
parent.right = new TreeNode(x);
}
}
public double findCloset(double [] array, int key)
{
for(double x : array)
{
insert(x);
}
//tree built
TreeNode t = root;
while(t!=null)
{
double x = t.value;
if( x > key )
{
if(t.left != null && Math.abs(t.left.value - key) < Math.abs(x - key))
{
t = t.left;
}else
{
return t.value;
}
}else
{
if(t.right != null && Math.abs(t.right.value - key) < Math.abs(x - key))
{
t = t.right;
}else
{
return t.value;
}
}
}
return 0;
}
}
public class findArray
{
public static void main(String[] arg)
{
BST b = new BST();
double []v = {1.2,3.4,5.6,1,4.5,6.7,3.2,2.9,3.1};
System.out.println(b.findCloset(v, 3));
}
}
Will this work?
- anonymous February 15, 2012{
public static double closest(Node node, double k, double k_closest) {
if(node.data == k) {
k_closest = k;
return k;
}
if(node.data > k) {
// handle to adjust k_closest
if((node.data - k) < Math.abs(k_closest - k))
k_closest = node.data;
if(node.left != null)
k_closest = closest(node.left, k, k_closest);
}
if(node.data < k) {
// handle to adjust k_closest
if(Math.abs(node.data - k) < Math.abs(k_closest - k))
k_closest = node.data;
if(node.right != null)
k_closest = closest(node.right, k , k_closest);
}
return(k_closest);
}
}