Minimum Distance Between BST Nodes

1/**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 *     int val;
5 *     TreeNode left;
6 *     TreeNode right;
7 *     TreeNode() {}
8 *     TreeNode(int val) { this.val = val; }
9 *     TreeNode(int val, TreeNode left, TreeNode right) {
10 *         this.val = val;
11 *         this.left = left;
12 *         this.right = right;
13 *     }
14 * }
15 */
16class Solution {
17    public int minDiffInBST(TreeNode root) {
18        Stack<TreeNode> stack = new Stack<TreeNode>();
19        TreeNode curr = root;
20        TreeNode prev = null;
21        int minDiff = 100000; // since 0 <= Node.val <= 10^5
22
23        // iterative inorder traversal will go through nodes
24        // in sorted order from smallest to largest.
25        while (curr != null || !stack.isEmpty()) {
26            if (curr != null) {
27                stack.push(curr);
28                curr = curr.left;
29            }
30            else {
31                curr = stack.pop();
32
33                if (prev != null) {
34                    minDiff = Math.min(minDiff, curr.val - prev.val);
35                }
36
37                prev = curr;
38                curr = curr.right;
39            }
40        }
41
42        return minDiff;
43    }
44}