Closest Value Search in Binary Search Tree (BST) means returning nearest value in BST to given key.
Following is simple algorithm for finding Closest Value in BST.
Step 1: Current root itself is NULL, then closest value is zero.
Step 2: If current root matches target key value, then closest value is key itself.
Step 3: Otherwise, consider current root as closest value and do following.
3.1: If key is smaller then current root, find closest value on left side tree of current root recursively and call it RecursiveClosest.
3.2: If key is larger then current root, find closest value on right side tree of current root recursively and call it RecursiveClosest.
Step 4: Return current root or RecusiveClosest depending on which ever is nearer to target key.
Step 2: If current root matches target key value, then closest value is key itself.
Step 3: Otherwise, consider current root as closest value and do following.
3.1: If key is smaller then current root, find closest value on left side tree of current root recursively and call it RecursiveClosest.
3.2: If key is larger then current root, find closest value on right side tree of current root recursively and call it RecursiveClosest.
Step 4: Return current root or RecusiveClosest depending on which ever is nearer to target key.
Following is implementation of above algorithm in c language.
Please write comments if you find anything wrong or you want to add something more related to this topic.
1 comment:
Very good information indeed. Thanks for posting this here. You can find more information on Binary search tree (BST) here in the following link with examples.
Binary search tree (BST) in Cpp with examples
Post a Comment
Write your comment here.