Algorithm Problem: Find Out the Minimum Number that Great or Equal to a Given Number In BST

By | 2013 年 1 月 1 日

Given a BST and a Number k, find out the minimum number p that p >= k.

The method is descriped below, in the code.

The recursive and non-recursive code is included.

```struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
};
TreeNode *findKRecursive(TreeNode *root, int k) {
if (NULL == root) {
//there is no node that match the requisite.
//在这颗空子树中是找不到目标的
return NULL;
}
if (root->val == k) {
//the node equal to k is find
//找到了正好等于k的节点，这就是全局要找的节点。
return root;
} else if (root->val < k) {
//root is less than k, so the result node is in it's right sub-tree, if there is.
//如果根节点的值小于k，那么唯一的满足条件的节点只能去右子树中查找，如果右子树中没有，那整棵树也没有。
return findKRecursive(root->right, k);
} else {
//root is > k, so the target node may be in it's left sub-tree, or is the current node.
//如果根节点的值>k，那么值更小的满足要求的节点可能出现在左子树中
TreeNode *knode = findKRecursive(root->left, k);
if (knode) {
//if a node is found in left sub-tree, then knode->value must <= cur->value, so return it
//如果左子树中确实找到了一个节点满足要求，那么他的值一定不大于当前节点的值
return knode;
} else {
//or there is no node which value is >= k, then , root is the best choice for the result.
//否则左子树中没有>=k的节点，那最小的满足>=k要求的节点就是root了。
return root;
}
}
}

TreeNode *findK(TreeNode *root, int k) {
TreeNode *lastFound = NULL;//record the last node found which value is >= k
TreeNode *cur = root;//current node to search for.
while (cur) {
if (cur->val == k) {
//the node equal to k is find
//找到了正好等于k的节点，这就是全局要找的节点。
return cur;
} else if (cur->val > k) {
//root is > k, so the result may be in it's left sub-tree, or cur is the best result
//如果根节点的值>k，那么值更小的满足要求的节点可能出现在左子树中，如果左子树没有的话，这就是最好的选择
lastFound = cur;
cur = cur->left;
} else {
//root is less than k, so the result node is in it's right sub-tree, if there is.
//如果根节点的值小于k，那么唯一的满足条件的节点只能去右子树中查找，如果右子树中没有，那整棵树也没有。
cur = cur->right;
}
}
return lastFound;
}
```