Closest Binary Search Tree Value

Problem

Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target. If there are multiple answers, print the smallest.

Constraints

• The number of nodes in the tree is in the range [1, 104].
• 0 <= Node.val <= 109
• -109 <= target <= 109

Solution

The problem Closest Binary Search Tree Value can be solved by implementing a min heap using a priority_queue and greater function. More specifically, it can be solved by iterating through the binary search tree using the given target value and pushing pairs of 2 values, difference between the node value and the target and the node value itself, to the container on each iteration. According to relational operators (pair), operator > perform a lexicographical comparison on the sequence formed by members first and second. In other words, a < b is processed as a.first < b.first || (!(a.first > b.first) && (a.second < b.second)). Therefore, when the iteration finishes, a pair with a smallest difference value will be on the top of the container, and if there are multiple pairs with the same value, then the one with a smallest node value will come out on top.

Implementation

typedef pair<double, int> Pair;

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
  public:
    int closestValue(TreeNode *root, double target)
    {
        priority_queue<Pair, vector<Pair>, greater<Pair>> pq;
        while (root != NULL)
        {
            if (target == root->val)
                return target;

            pq.push(make_pair(abs(root->val - target), root->val));
            root = target < root->val ? root->left : root->right;
        }

        return pq.top().second;
    }
};