LeetCode Entry

530. Minimum Absolute Difference in BST

14.06.2023 easy 2023 kotlin

Min difference in a BST

530. Minimum Absolute Difference in BST easy blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/245

Problem TLDR

Min difference in a BST

Intuition

In-order traversal in a BST gives a sorted order, we can compare curr - prev.

Approach

Let’s write a Morris traversal: make the current node a rightmost child of its left child.

Complexity

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(1)\)

Code


fun getMinimumDifference(root: TreeNode?): Int {
    if (root == null) return 0
    var minDiff = Int.MAX_VALUE
    var curr = root
    var prev = -1
    while (curr !=  null) {
        val left = curr.left
        if (left != null) {
            var leftRight = left
            while (leftRight.right != null) leftRight = leftRight.right
            leftRight.right = curr
            curr.left = null
            curr = left
        } else {
            if (prev >= 0) minDiff = minOf(minDiff, curr.`val` - prev)
            prev = curr.`val`
            curr = curr.right
        }
    }
    return minDiff
}