# 14.06.2023 [530. Minimum Absolute Difference in BST]

Min difference in a BST

14.06.2023

530. Minimum Absolute Difference in BST easy
blog post

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
}