Minimum Distance Between BST Nodes

Problem Id: 783 Difficulty: Easy Tag: Tree Tag: Recursion


Intuition

Just use inorder traversal to visit each node in ascending order, and compare the existing minimum diff with the diff of current node and last visited node.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def minDiffInBST(self, root: TreeNode) -> int:
        self.last = float('-inf')
        self.min_diff = float('inf')
        self._inorder(root)
        return self.min_diff

    def _inorder(self, node):
        if node is None:
            return
        self._inorder(node.left)
        self.min_diff = min(self.min_diff, node.val - self.last)
        self.last = node.val
        self._inorder(node.right)