# 530. Minimum Absolute Difference in BST

Reference: LeetCode
Difficulty: Easy

## Problem

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Note: There are at least two nodes in this BST.

Example:

## Analysis

Methods:

1. Brute-Force
• Push into a sorted array.
• Time: $O(N)$
• Space: $O(N)$
2. Inorder Traversal
• We need to use the fact that the tree is a BST and inorder traversal will generate sequence in order.
• We compare each nodes with the previous if it exists, and update the minimum difference value if necessary.
• Time: $O(N)$
• Space: $O(h)$
3. Preorder Traversal
• We can apply preorder traversal, but this time when traversing the tree, we update pred if going right, or succ if going left.
• During visiting the node, we compare the node’s value with pred and succ, and update the minimum difference value if necessary.
• Time: $O(N)$
• Space: $O(h)$

## Code

### Inorder

Note:

• Initialize prev with null, since we don’t compare at the beginning.
• Use Math.min instead of comparison operation.
• Don’t forget to update prev.

### Preorder

Note:

• Initialize pred and succ with null.

Comment Junhao Wang
a software engineering cat