530 Minimum Absolute Difference in BST

1. Description

Given the root of Binary Search Tree (BST), return the minimum difference between the values of any two different nodes in the tree.

 

constraints :

• The number of nodes in the tree is in the range [2, \(10^{4}\)].
• 0 <= Node.val <= \(10^{5}\)

 

2. Algorithms

To store all values of nodes into one array, we need to traverse through the tree. If we use inorder tree traversal, we can get sorted values of array.

 

Because the array from tree is sorted, we just compare the difference of adjacent values repeatedly.

 

1. Start
2. Declare variable named inorder initialized with empty list.
3. Declare function named helper which got root as input.
   1. If root,
      1. Traverse left child of root recursively.
      2. Append the value of root to list.
      3. Traverse right child of root recursively.
4. Operate helper function.
5. Declare variable named min_diff initialized with 2**32.
6. Repeat the steps through integers 1 to len(inorder) - 1.
   1. Calculate diff of integer[i] and integer[i + 1].
   2. Update min_diff as min between min_diff and diff.
7. Return min_diff after the loop ends.
8. End

3. Codes

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        # inorder : list, stores the value of input tree in sorted format. 
        inorder = [] 
        def helper(root) : 
            if root : 
                helper(root.left) 
                inorder.append(root.val)
                helper(root.right) 
                
        helper(root)
        min_diff = 2**32
        for i in range(len(inorder) - 1) : 
            diff = inorder[i+1] - inorder[i] 
            min_diff = min(min_diff, diff) 
        return min_diff

 

4. Conclusion