LC-0783 Easy LeetCode

783. Minimum Distance Between BST Nodes

Tree Depth-First Search Breadth-First Search Binary Search Tree Binary Tree

Read the full problem statement on LeetCode.

Difficulty: easy Acceptance: 60% Topics: Tree, Depth-First Search, Breadth-First Search, Binary Search Tree, Binary Tree

View full problem on LeetCode

Reading material

Trees & Traversals 18 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(h)

class Solution(object):
    def minDiffInBST(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def dfs(node):
            if not node:
                return
            dfs(node.left)
            self.result = min(self.result, node.val-self.prev)
            self.prev = node.val
            dfs(node.right)

        self.prev = float('-inf')
        self.result = float('inf')
        dfs(root)
        return self.result

Solution from kamyu104/LeetCode-Solutions · MIT