Minimum Difference Between BST Nodes

This is one of the easier problems to test your Data structures knowledge. I picked
it up from leetcode.

Here's the problem statement:

Given a Binary Search Tree (BST) with the root node root,
return the minimum difference between the values of any two different nodes in the tree.

example:

For the following given binary search tree
                       4
                     /   \
                  2       6
                /   \
              1      3

The minimum difference is 1, between nodes with value 1 and 2 as well as between
nodes with values 2 and 3.

Idea 1:
Iterate over the BST in an inorder fashion and save the numbers in a vector.
The smallest difference is going to be between two adjacent numbers.

Idea 2:
Another idea to attack the problem is to utilize the fact that if we do an in-order
traversal of the BST, we'll get the values in ascending order. 

Based on idea 2 above, we'll employ recursive in-order solution and augment the algorithm to keep two more 'facts' (invariants) at each state of the recursion-tree

• What is the value of the predecessor we've seen, to compare with the current value
• What is the minimum difference seen so far.

Following is the solution:

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	const int64_t INF = numeric_limits::max();
	class Solution {
	public:
	int minDiffInBST(TreeNode* root) {
	int64_t min_diff = INF;
	int64_t pred_val = INF;
	minDiff(root, pred_val, min_diff);
	//min_diff = min( min_diff, abs(prev_val -
	return min_diff;
	}
	private:
	void minDiff(TreeNode* root, int64_t& pred_val, int64_t& min_diff) {
	if (!root) return ;
	minDiff(root->left, pred_val, min_diff);
	min_diff = min(min_diff, abs(pred_val - root->val));
	pred_val = root->val;
	minDiff(root->right, pred_val, min_diff);
	}
	};

view raw min_difference.cpp hosted with ❤ by GitHub