Wednesday, June 26, 2013

Find Ceiling of a Number in BST

[Question]
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