Closest Binary Search Tree Value - Practice Coding Problems

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 values with the same minimum difference, return the smallest value.

Example:

For BST [4,2,5,1,3] and target 3.714286, the closest value is 4.

Input & Output

Example 1 — Basic BST

$ Input: root = [4,2,5,1,3], target = 3.714286

› Output: 4

💡 Note: The differences are: |4-3.714286|=0.286, |2-3.714286|=1.714, |5-3.714286|=1.286, |1-3.714286|=2.714, |3-3.714286|=0.714. The closest value is 4.

Example 2 — Exact Match

$ Input: root = [1,null,2], target = 2.0

› Output: 2

💡 Note: Target 2.0 exactly matches node value 2, so return 2.

Example 3 — Tie Breaker

$ Input: root = [1,null,3], target = 2.0

› Output: 1

💡 Note: |1-2|=1 and |3-2|=1. Both have same distance, return smaller value 1.

Constraints

The number of nodes in the tree is in the range [1, 10⁴]
0 ≤ Node.val ≤ 10⁹
-10⁹ ≤ target ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input BST

Binary search tree [4,2,5,1,3] with target = 3.714

Calculate Distances

Find absolute differences: |4-3.714|, |2-3.714|, etc.

Return Closest

Node 4 has minimum distance of 0.286

Key Takeaway

🎯 Key Insight: Use BST property to navigate efficiently towards target while tracking closest value

Asked in

G Google 15 f Facebook 12 a Amazon 8 M Microsoft 6

The key insight is to leverage the BST property for efficient navigation. Instead of visiting all nodes, we can navigate directly towards the target while tracking the closest value. The optimal approach uses iterative BST traversal in O(h) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Traverse All Nodes	O(n)	O(h)	Visit every node in the tree and find the one with minimum distance to target
Binary Search Tree Navigation	O(h)	O(1)	Use BST property to navigate towards target and track closest value

Brute Force - Traverse All Nodes — Algorithm Steps

Step 1: Traverse all nodes using DFS
Step 2: Calculate |node.val - target| for each node
Step 3: Keep track of minimum difference and corresponding value

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin DFS from root, target = 3.714

Visit All

Check every node: |4-3.714|=0.286, |2-3.714|=1.714, etc.

Result

Node 4 has minimum difference of 0.286

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <float.h>
#include <math.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

double minDiff;
int closest;

void dfs(struct TreeNode* node, double target) {
    if (!node) return;
    
    double diff = fabs(node->val - target);
    if (diff < minDiff || (diff == minDiff && node->val < closest)) {
        minDiff = diff;
        closest = node->val;
    }
    
    dfs(node->left, target);
    dfs(node->right, target);
}

int solution(struct TreeNode* root, double target) {
    minDiff = DBL_MAX;
    closest = 0;
    dfs(root, target);
    return closest;
}

struct TreeNode* createNode(int val) {
    struct TreeNode* node = malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    // Simple test case
    struct TreeNode* root = createNode(4);
    root->left = createNode(2);
    root->right = createNode(5);
    root->left->left = createNode(1);
    root->left->right = createNode(3);
    
    double target = 3.714286;
    printf("%d\n", solution(root, target));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit all n nodes in the tree

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth h (height of tree)

✓ Linear Space

58.2K Views

Medium Frequency

~15 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Traverse All Nodes — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler