Minimum Distance Between BST Nodes

Problem Summary

• Given a BST, return minimum difference between any two nodes

Approach Taken

• if the input is sorted, for example: [1,2,3,5,6]
• then min diff is basically checking for two side by side nums
  • could be done via Two Pointers in the Same Direction
  • however, sorting is $O(nlogn)$
• since this is a Binary Search Tree
• the In-order Traversal of it is sorted

Main Concepts Used

• Trees
• Tree Traversal
• Binary Search Tree
• In-order Traversal

Time & Space Complexity

• Time: $O(n)$ → Reason: Going through each node just once
• Space: $O(h)$ → Reason: Height of the tree for the recursive call stack. $O(n)$ for unbalanced tree in the worst case.

Code

class Solution:
    def minDiffInBST(self, root: Optional[TreeNode]) -> int:
        self.minDifference = float("inf")
        self.prev = float("inf")

        def inOrder(root):
            if not root:
                return

            inOrder(root.left)
            self.minDifference = min(self.minDifference, abs(self.prev - root.val))
            self.prev = root.val
            inOrder(root.right)

        inOrder(root)
        return self.minDifference

Common Mistakes / Things I Got Stuck On

• Had the right idea initially on sorted array input this could be done with two pointers in $O(n)$ but didn't realize its a BST and an inorder traversal would lead to sorted array automatically.