[Leetcode] 270. Closest Binary Search Tree Value

initial

no idea and demotivated

so question is asking in a BST, which node has the closest value to a target value. So if

 # Example 1: Tree = [4,2,5,1,3], target = 3.714286
    #       4
    #      / \
    #     2   5
    #    / \
    #   1   3

ans should be 4.

main logic is instead of taversing each node, we know BST is sorted so left node is smaller than root.

So while traversing, if the current node's value - target has a smaller difference than what we have seen before, we should update answer node as that current node.

one impt bit is question also said If there are multiple answers, return the smallest. So if target=3.5 we need to return 3. So we need to check elif statement

            elif abs(root.val-target)==abs(ans-target):
                ans=min(ans,root.val)

sol

class SolutionAlt:
    def closestValue(self, root: TreeNode, target: float) -> int:
        ans = root.val

        while root:
            if abs(root.val-target)<abs(ans-target):
                ans=root.val
            elif abs(root.val-target)==abs(ans-target):
                ans=min(ans,root.val)
            if root.val>target:
                root=root.left
            else:
                root=root.right
        return ans

complexity

n time
space depends on the recursion depth so log n if balanced and n if skewed (wrong)

wrong! its iterative not recursive so its actually just 1 space