How hard is LeetCode 270. Closest Binary Search Tree Value?

LeetCode 270. Closest Binary Search Tree Value is rated Easy on LeetCode.

What is the time complexity of LeetCode 270. Closest Binary Search Tree Value?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 270. Closest Binary Search Tree Value?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 270. Closest Binary Search Tree Value cover?

LeetCode 270. Closest Binary Search Tree Value is tagged Tree, Depth-First Search, Binary Search Tree, Binary Search and Binary Tree on LeetCode.

Is LeetCode 270. Closest Binary Search Tree Value a premium problem?

Yes. LeetCode 270. Closest Binary Search Tree Value is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Closest Binary Search Tree Value — LeetCode 270 Python Solution

EasyLeetCode PremiumTreeDepth-First SearchBinary Search TreeBinary SearchBinary Tree

Problem: #270
Pattern: Monotonic Stack
Reading time: 4 min
Source: leetcode.com

The 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.

Example

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

Python solution

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def closestValue(self, root: Optional[TreeNode], target: float) -> int:
        def dfs(node: Optional[TreeNode]):
            if node is None:
                return
            nxt = abs(target - node.val)
            nonlocal ans, diff
            if nxt < diff or (nxt == diff and node.val < ans):
                diff = nxt
                ans = node.val
            node = node.left if target < node.val else node.right
            dfs(node)

        ans = 0
        diff = inf
        dfs(root)
        return ans

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Monotonic Stack

Answer "what is the next greater element" for every position in one pass. LeetCode 270. Closest Binary Search Tree Value is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 270. Closest Binary Search Tree Value?: LeetCode 270. Closest Binary Search Tree Value is rated Easy on LeetCode.
What is the time complexity of LeetCode 270. Closest Binary Search Tree Value?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 270. Closest Binary Search Tree Value?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 270. Closest Binary Search Tree Value cover?: LeetCode 270. Closest Binary Search Tree Value is tagged Tree, Depth-First Search, Binary Search Tree, Binary Search and Binary Tree on LeetCode.
Is LeetCode 270. Closest Binary Search Tree Value a premium problem?: Yes. LeetCode 270. Closest Binary Search Tree Value is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.