Question

Given a BST, find the node that is larger/smaller than particular number

Or the question can be:

Given a binary search tree and a value k, please find a node in the binary search tree whose value is closest to k. link

Analysis

This post is based on the second question above.

1. Traverse the tree top-down.
2. While traversing, record values that are closer to target than previously-found value.
3. If found, the target, break and return. source

Code

From this post.

BinaryTreeNode* getClosestNode(BinaryTreeNode* pRoot, int value)
{
    BinaryTreeNode* pClosest = NULL;
    int minDistance = 0x7FFFFFFF;
    BinaryTreeNode* pNode = pRoot;
    while(pNode != NULL){
        int distance = abs(pNode->m_nValue - value);
        if(distance < minDistance){
            minDistance = distance;
            pClosest = pNode;
        }

        if(distance == 0)
            break;

        if(pNode->m_nValue > value)
            pNode = pNode->m_pLeft;
        else if(pNode->m_nValue < value)
            pNode = pNode->m_pRight;
    }

    return pClosest;
}