Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

LeetCode: Closest Binary Search Tree Value

Posted on February 16, 2018July 26, 2020 by braindenny

Closest Binary Search Tree Value



Similar Problems:

  • Closest Binary Search Tree Value II
  • CheatSheet: Leetcode For Code Interview
  • CheatSheet: Common Code Problems & Follow-ups
  • Tag: #binarytree, #recursive

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:
Given target value is a floating point.
You are guaranteed to have only one unique value in the BST that is closest to the target.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


## https://code.dennyzhang.com/closest-binary-search-tree-value
## Basic Ideas: binary search
##
##  After checking the root, only need to check either left or right subtree
##
## Complexity: Time O(log(n)), Space O(1)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def closestValue(self, root: TreeNode, target: float) -> int:
        res = root.val
        while root:
            res = min(res, root.val, key=lambda x: abs(x-target))
            if target > root.val:
                root = root.right
            else:
                root = root.left
        return res
## https://code.dennyzhang.com/closest-binary-search-tree-value
## Basic Ideas:
##    If the exact match, return
##    If current node is bigger than the target, we get a starting value.
##        Then check left sub-tree
##    If smaller, get a starting value. Then check right sub-tree
##
## Complexity: Time O(log(n)), Space O(1)
##
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def closestValue(self, root, target):
        """
        :type root: TreeNode
        :type target: float
        :rtype: int
        """
        if root is None: return None
        res = root.val
        min_diff = abs(target - root.val)
        if min_diff == 0: return res
        check_left, check_right = False, False
        if root.val > target:
            # no need to explore the right
            check_left = True
        else:
            check_right = True

        if check_left and root.left:
            l_closest = self.closestValue(root.left, target)
            if abs(target - l_closest) < min_diff:
                res = l_closest

        if check_right and root.right:
            r_closest = self.closestValue(root.right, target)
            if abs(target - r_closest) < min_diff:
                res = r_closest

        return res
linkedin
github
slack

Post Views: 8
Posted in BasicTagged #binarytree, #classic, #recursive, binarysearch

Post navigation

LeetCode: Customer Placing the Largest Number of Orders
LeetCode: Closest Binary Search Tree Value II

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.