LeetCode Entry
783. Minimum Distance Between BST Nodes
Let's write Morris Traversal. Store current node at the rightmost end of the left children.
783. Minimum Distance Between BST Nodes easy
fun minDiffInBST(root: TreeNode?): Int {
var prev: TreeNode? = null
var curr = root
var minDiff = Int.MAX_VALUE
while (curr != null) {
if (curr.left == null) {
if (prev != null) minDiff = minOf(minDiff, Math.abs(curr.`val` - prev.`val`))
prev = curr
curr = curr.right
} else {
var right = curr.left!!
while (right.right != null && right.right != curr) right = right.right!!
if (right.right == curr) {
right.right = null
curr = curr.right
} else {
right.right = curr
val next = curr.left
curr.left = null
curr = next
}
}
}
return minDiff
}
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/121
Intuition
Given that this is a Binary Search Tree, inorder traversal will give us an increasing sequence of nodes. Minimum difference will be one of the adjacent nodes differences.
Approach
Let’s write Morris Traversal. Store current node at the rightmost end of the left children.
Complexity
- Time complexity: \(O(n)\)
- Space complexity: \(O(1)\)