How hard is LeetCode 530. Minimum Absolute Difference in BST?

LeetCode 530. Minimum Absolute Difference in BST is rated Easy on LeetCode.

What is the time complexity of LeetCode 530. Minimum Absolute Difference in BST?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 530. Minimum Absolute Difference in BST?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 530. Minimum Absolute Difference in BST cover?

LeetCode 530. Minimum Absolute Difference in BST is tagged Tree, Depth-First Search, Breadth-First Search, Binary Search Tree and Binary Tree on LeetCode.

Minimum Absolute Difference in BST — LeetCode 530 Python Solution

EasyTreeDepth-First SearchBreadth-First SearchBinary Search TreeBinary Tree

Problem: #530
Pattern: Tree Traversal
Reading time: 4 min
Source: leetcode.com

The problem

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

Example

Input: root = [4,2,6,1,3]
Output: 1

Python solution

Python

# 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:
        def dfs(root: Optional[TreeNode]):
            if root is None:
                return
            dfs(root.left)
            nonlocal pre, ans
            ans = min(ans, root.val - pre)
            pre = root.val
            dfs(root.right)

        pre = -inf
        ans = inf
        dfs(root)
        return ans

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Tree Traversal

Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 530. Minimum Absolute Difference in BST is filed here because LeetCode tags it Tree, Binary Tree and Binary Search Tree, which is the vocabulary this hub collects.

The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.

On a study list

This problem is on Top Interview 150.

Frequently asked questions

How hard is LeetCode 530. Minimum Absolute Difference in BST?: LeetCode 530. Minimum Absolute Difference in BST is rated Easy on LeetCode.
What is the time complexity of LeetCode 530. Minimum Absolute Difference in BST?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 530. Minimum Absolute Difference in BST?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 530. Minimum Absolute Difference in BST cover?: LeetCode 530. Minimum Absolute Difference in BST is tagged Tree, Depth-First Search, Breadth-First Search, Binary Search Tree and Binary Tree on LeetCode.