No. 45 – Closest Node in a Binary Search Tree

Problem: Given a binary search tree and a value k, please find a node in the binary search tree whose value is closest to k.

参考:http://codercareer.blogspot.com/2013/03/no-45-closest-node-in-binary-search-tree_2.html

/* Copyleft: Ming Lin <minggr@gmail.com> */

#include <stdio.h>
#include "tree.h"

int distance(int i, int j)
{
	int d = i - j;

	if (d < 0)
		d = -d;

	return d;
}

struct node *closest_node(struct node *root, int key)
{
	struct node *n, *closest_n = NULL;
	int cur_d, min_d;

	cur_d = min_d = distance(root->data, key);

	n = root;
	while (n) {
		if (key == n->data)
			return n;

		cur_d = distance(n->data, key);
		if (n == root || cur_d < min_d) {
			min_d = cur_d;
			closest_n = n;
		}

		if (key > n->data)
			n = n->right;
		else
			n = n->left;
	}

	return closest_n;
}

int main()
{
	struct node *root, *closest;
	int postorder[] = {14, 21, 25, 31, 28, 24, 39, 36, 47, 41, 32};
	int n = 11;
	int key = 29;

	root = construct_bst(postorder, 0, n-1);	
	closest = closest_node(root, key);
	printf("key %d, closest %d\n", key, closest->data);

	return 0;
}

 

 

Leave a Reply