from lintcode import (
    TreeNode,
)

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: the given BST
    @param target: the given target
    @return: the value in the BST that is closest to the target
    """
    def closest_value(self, root: TreeNode, target: float) -> int:
        # write your code here
        if not root:
            return -1

        upper = float("inf")
        lower = float("-inf") 

        stack = collections.deque([root])
        while stack:
            node = stack.pop()
            if node.val > target:
                upper = min(node.val, upper)
                if node.left:
                    stack.append(node.left)
            elif node.val < target:
                lower = max(node.val, lower)
                if node.right:
                    stack.append(node.right)
            else: # same value
                return node.val

        return upper if (upper - target < target - lower) else lower