[Top Interview 150] 530. Minimum Absolute Difference in BST

Solution)

class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
    	# Initialization
        prev, res = None, float("inf")
        
        # Depth-First-Search
        def dfs(node):
            # Base Case
            if not node:
                return
            
            # Adjusting the scope
            nonlocal prev, res

            # Left Subtree
            dfs(node.left)

            # Recursive Call
            if prev:
                res = min(res, node.val - prev.val)
            prev = node

            # Right Subtree
            dfs(node.right)
        
        dfs(root)
        return res

 
Problem: LeetCode
Reference: NeetCode
 
Time Complexity: O(n)
Space Complexity: O(1)
 
*n = number of nodes

Explanation)

As we're given a bst (binary search tree), we'll use an inorder traversal to compare nodes in a sorted order. 
 

 

inorder traversal

With the inorder traversal, we can find the minimum difference by comparing the difference between the adjacent nodes.
 
 

Initialization)

To compare the adjacent nodes while traversing the tree, you need a variable that saves a previous node. 
 
Also, have a variable that will save the minimum differences while traversing. The initial value will be a positive infinity because when we compare the first difference with the initial res, we want to make sure that the first difference will replace the positive infinity. 
 

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

 
 

Base Case)

If there isn't a node in a tree, a difference doesn't exit thus we'll simply return.
 

def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        prev, res = None, float("inf")
        
        def dfs(node):
            if not node:
                return

 
 

Nonlocal)

Since our dfs() function is an inner function and we're trying to use variables that are defined between functions, we have to adjust the socpe of the variables (especially when we're trying to adjust the values).
 
So let's use the keyword nonlocal to use prev and res in an inner function.
 

def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        prev, res = None, float("inf")
        
        def dfs(node):
            if not node:
                return
            
            nonlocal prev, res

 
 

Recursive Calls)

Since we're doing an inorder traversal, the order of the recursive calls would be
 
1) left subtree
2) root node
3) right subtree
 
When the root node step is reached during the recursion, it'll check if prev is not Null (since the initial value was Null) then find and compare the differences.
 
Once the smaller difference is decided, we'll update prev to the current root node, because we need to find the difference between the current root node and the future adjacent node. 
 
Call this dfs() function and return res.
 

def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        prev, res = None, float("inf")
        
        def dfs(node):
            if not node:
                return
            
            nonlocal prev, res

            dfs(node.left)

            if prev:
                res = min(res, node.val - prev.val)
            prev = node

            dfs(node.right)
        
        dfs(root)
        return res

 
 
 
TMI)
With this problem, I learned how you have to switch the steps in recursion according to which traversal you're using. I'm still confused with when I have to use a helper function. Hopefully solving these problems will eventually help me master binary tree / recursion :]