530.minimum-absolute-difference-in-bst.md

530. Minimum Absolute Difference in BST

Inorder Traversal (Extra Space)

private val inorder = mutableListOf<Int>()

fun getMinimumDifference(root: TreeNode?): Int {
    traversal(root)
    var minDiff = Int.MAX_VALUE
    for (i in 1 until inorder.size) {
        minDiff = min(minDiff, inorder[i] - inorder[i - 1])
    }
    return minDiff
}

private fun traversal(root: TreeNode?) {
    if (root == null) return
    traversal(root.left)
    inorder.add(root.`val`)
    traversal(root.right)
}

• Time Complexity: O(n).
• Space Complexity: O(n).

Inorder Traversal (Without Extra Space)

private var result = Int.MAX_VALUE
private var prev: Int? = null

fun getMinimumDifference(root: TreeNode?): Int {
    dfs(root)
    return result
}

private fun dfs(root: TreeNode?) {
    if (root == null) return
    dfs(root.left)
    if (prev != null) {
        result = min(result, abs(prev - root.`val`))
    }
    prev = root.`val`
    dfs(root.right)
}

• Time Complexity: O(n).
• Space Complexity: O(h).

Failed Case

// answer = 9
      236
     /   \
   104   701
     \      \
     227   911