A binary search tree is given. Find the ceiling value present in the BST of
a given key. eg-
8
3 12
2 6 10 15
4
key - 13 => 15
key - 4 =>6
key - 8 =>10
[Analysis]
Using in-order traversal. The time complexity is O(lgN) on average, O(N) at the worst case.
[Code]
class TreeNode {
public:
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int v): val(v), left(NULL), right(NULL) {};
};
//
// return the pointer when a ceiling is found;
// otherwise, NULL;
//
TreeNode* find_ceiling(TreeNode* root, int target)
{
if (root==NULL) return NULL;
if (root->val == target) return root;
if (root->val > target) {
TreeNode* temp = find_ceiling( root->left, target );
return (temp==NULL)? root: temp;
}
return find_ceiling( root->right, target );
}
No comments:
Post a Comment