Introduction

In this blog post, we will explore how to solve the LeetCode problem "783" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Given the root of a Binary Search Tree (BST), return the minimum difference between the values of any two different nodes in the tree. Example 1: Input: root = [4,2,6,1,3] Output: 1 Example 2: Input: root = [1,0,48,null,null,12,49] Output: 1 Constraints: The number of nodes in the tree is in the range [2, 100]. 0 <= Node.val <= 105 Note: This question is the same as 530: https://leetcode.com/problems/minimum-absolute-difference-in-bst/

Explanation

Here's an efficient solution to find the minimum difference between any two nodes in a BST:

• Inorder Traversal: Perform an inorder traversal of the BST. This ensures that the nodes are visited in sorted order.
• Track Previous Value: Keep track of the previously visited node's value during the traversal.

• Calculate Difference: For each node, calculate the difference between its value and the previous node's value. Update the minimum difference found so far.

• Runtime Complexity: O(N), where N is the number of nodes in the BST.

• Storage Complexity: O(H), where H is the height of the BST (due to the recursion stack). In the worst case (skewed tree), H = N. In the best case (balanced tree), H = log N.

Code

    from typing import Optional

# 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:
        self.min_diff = float('inf')
        self.prev_val = None

        def inorder(node: Optional[TreeNode]):
            if not node:
                return

            inorder(node.left)

            if self.prev_val is not None:
                self.min_diff = min(self.min_diff, node.val - self.prev_val)

            self.prev_val = node.val
            inorder(node.right)

        inorder(root)
        return self.min_diff