270.Closest Binary Search Tree Value

Tags: [tree], [binary_tree], [binary_search_tree], [BST], [predecessor], [successor], [float]

Com: {g}

Hard: [##]

Link: https://leetcode.com/problems/closest-binary-search-tree-value/#/description

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.

Solution: Predecessor, Successor

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def closestValue(self, root, target):
        """
        :type root: TreeNode
        :type target: float
        :rtype: int
        """
        if not root or target is None:
            return None

        curr = root
        while curr:
            if abs(curr.val - target) < 0.0001:
                return curr.val
            elif target < curr.val:
                if not curr.left:
                    return curr.val
                else:
                    predecessor = self.get_predecessor(curr)
                    pre = predecessor.val
                    mid = float(pre) + float(curr.val - pre) / 2.0
                    if target > mid:
                        return curr.val
                    elif pre < target < mid:
                        return pre
                    else:
                        curr = curr.left
            else:
                if not curr.right:
                    return curr.val
                else:
                    successor = self.get_successor(curr)
                    suc = successor.val
                    mid = float(curr.val) + float(suc - curr.val) / 2.0
                    if target < mid:
                        return curr.val
                    elif mid < target < suc:
                        return suc
                    else:
                        curr = curr.right

        return None

    def get_predecessor(self, root):
        curr = root.left
        while curr.right:
            curr = curr.right

        return curr

    def get_successor(self, root):
        curr = root.right
        while curr.left:
            curr = curr.left

        return curr

Revelation:

• When we calculate the mid, we need find the current node's predecessor and successor.

Note:

• Time Complexity = O(lgn), n is the number of nodes in the give BST.