[Leetcode] 530. Minimum Absolute Difference in BST

https://leetcode.com/problems/minimum-absolute-difference-in-bst/description/?envType=study-plan-v2&envId=top-interview-150

initial

my initial logic was just checking the parent and direct child's values and getting the minimum. But this is wrong cuz there can be nodes far apart that have abs difference that is small.

    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        ans = int(10e16)
        def search(now,prev):
            nonlocal ans
            if not now:
                return
            ans = min(ans, abs(prev.val-now.val))
            if ans==1:
                return 1
                exit()
            search(now.left,now)
            search(now.right,now)
        search(root.left,root)
        search(root.right,root)
        return ans

solution

So i saw solution and inorder traversal(left->root-->right) is guaranteed to search in ascending order of nodes' values. So I tried implementing inorder but I made another mistake.

notice

            inorder(now.left)
            if not prev:
                prev = now
                return
            ans = min(ans, abs(prev.val-now.val))
            prev=now
            inorder(now.right)

But see that if prev is None, we return right away and dont continue traversing the right side. So for cases like

    1
     \
      3
     /
    2

Call inorder(1)

No left child → nothing happens.

prev is None, so prev = 1, then return early!

❌ It never reaches node 2 or 3.

Also return 1 and exit() is redundant cuz exit() is never reached.

so correct sol is

def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
    ans = float('inf')
    prev = None

    def inorder(now):
        nonlocal ans, prev
        if not now:
            return
        inorder(now.left)
        if prev is not None:
            ans = min(ans, abs(prev.val - now.val))
        prev = now
        inorder(now.right)

    inorder(root)
    return ans

complexity

o(n) time
I thought its o(1) space but for recursion, space depends on recursion depth.

You're right to focus on the ans and prev variables because they use a constant amount of extra memory regardless of the size of the tree. The space complexity related to the depth of recursion comes from something less obvious: the function call stack.

Let's break down what happens when a function calls itself recursively:

Function Call: When inorder(node) is called, the computer needs to store information about this specific call. This includes:

The current value of the parameters (node in this case).
The return address (where to go back to after the function call finishes).
Local variables used within that specific call (though in our inorder function, the main local variables ans and prev are nonlocal, meaning they belong to the outer scope).
The current state of the execution.