How hard is LeetCode 783. Minimum Distance Between BST Nodes?

LeetCode 783. Minimum Distance Between BST Nodes is rated Easy on LeetCode.

What is the time complexity of LeetCode 783. Minimum Distance Between BST Nodes?

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

What is the space complexity of LeetCode 783. Minimum Distance Between BST Nodes?

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

What topics does LeetCode 783. Minimum Distance Between BST Nodes cover?

LeetCode 783. Minimum Distance Between BST Nodes is tagged Tree, Depth-First Search, Breadth-First Search, Binary Search Tree and Binary Tree on LeetCode.

Minimum Distance Between BST Nodes — LeetCode 783 Python Solution

EasyTreeDepth-First SearchBreadth-First SearchBinary Search TreeBinary Tree

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

The problem

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

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 minDiffInBST(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 783. Minimum Distance Between BST Nodes 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.

Frequently asked questions

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