Interview Question
Country: United States
For a given subtree, there are 3 cases:
(1)root is NULL, then no such node in this subtree
(2)root->val < K, then the result might be in the root's right subtree or just root itself
(3)root->val >= K, then the result could only be in the root's left subtree
Following is C code:
TreeNode* findNextSmallerInBST(TreeNode* root, int K)
{
if(root == NULL) return NULL;
else if(root->val < K){
TreeNode* t = findNextSmallerInBST(root->right, K);
return t != NULL ? t : root;
}
else return findNextSmallerInBST(root->left, K);
}
- Anonymous February 20, 2014