Minimum Absolute Difference in BST

Problem Summary

Given a Binary Search Tree, return the absolute minimum difference between any two nodes

What is Being Asked?

Clone of Minimum Distance Between BST Nodes

Approach Taken

if the input is sorted, for example: [1,2,3,5,6]
then min diff is basically checking for two side by side nums
- could be done via Two Pointers in the Same Direction
- however, sorting is $O (n l o g n)$
since this is a Binary Search Tree
the In-order Traversal of it is sorted

Main Concepts Used

Time & Space Complexity

Time: $O (n)$ → Reason: Visiting each node once
Space: $O (h)$ → Reason: For unbalanced tree the height could be $O (n)$

Code

class Solution:
    def __init__(self):
        self.result = float("inf")
        self.prev = float("inf")

    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        self.helper(root)
        return self.result

    def helper(self, root):
        if not root:
            return

        self.helper(root.left)
        self.result = min(abs(self.prev - root.val), self.result)
        self.prev = root.val
        self.helper(root.right)