Leetcode 783. Minimum Distance Between BST Nodes
Problem Explanation
The problem is asking to find the minimum difference among two different nodes in a Binary Search Tree. To find that, we can use the in-order traversal. A Binary Search Tree (BST) has the property that all nodes on the left subtree are less than the node and all nodes on the right are greater. Therefore, performing an in-order traversal (i.e., left-root-right), which sorts the BST in ascending order, can allow us to easily access adjacent values.
We only compare the current node with its immediate predecessor in the in-order sequence, making the problem more manageable.
Approach
This solution walks through the Binary Search Tree (BST) in an in-order traversal approach. By walking in-order, we are guaranteed to go from the smallest to the largest node because of the property of BST. We keep track of the previous node we passed, calculate the difference with the current node, and keep the minimum of all the differences.
Let's walk through an example.
Example: Input: root = [4,2,6,1,3,null,null]
This tree can be represented as:
1 2 3 4 4 / \ 5 2 6 6 / \ 7 1 3
The nodes in in-order traversal are: 1,2,3,4,6. And the differences are: abs(1-2), abs(2-3), abs(3-4), and abs(4-6). The minimum of these differences is 1. This result will be returned as output.
C++ Solution
1
2C++
3class Solution {
4 public:
5 int minDiffInBST(TreeNode* root) {
6 int ans = INT_MAX; //Initialize answer variable with maximum integer
7 inorder(root, ans); //start with root node, pass answer reference to function
8 return ans; //return answer value
9 }
10
11 private:
12 int pred = -1; //Predecessor of current node
13
14 void inorder(TreeNode* root, int& ans) {
15 if (root == nullptr) // if node is null, return
16 return;
17
18 inorder(root->left, ans); //recursive call to left node
19 if (pred >= 0) //if predecessor is not null, calculate minimum difference
20 ans = min(ans, root->val - pred);
21 pred = root->val; //update predecessor to current node
22 inorder(root->right, ans); //recursive call to right node
23 }
24};
Python Solution
1 2Python 3class Solution: 4 def minDiffInBST(self, root): 5 self.res = float('inf') # Initialize result with maximum value 6 self.pre = None # Initialize predecessor with None 7 self.inOrder(root) #start process from root 8 return self.res #return result 9 10 def inOrder(self, root): 11 if root: #if root node is not None, 12 self.inOrder(root.left) #recursive call to left node 13 if self.pre: #if predecessor is not None, calcualte minimum difference 14 self.res = min(self.res, root.val - self.pre.val) 15 self.pre = root #update predecssor with current node 16 self.inOrder(root.right) #recursive call to right node
Note
Java, JavaScript, and C# solutions are not required. But you can easily implement the above Python or C++ solution in your preferred programming language by following the same logic. Just make sure to use equivalent syntax and data structures of that language.# Java Solution
Similar to the Python and C++ solutions, we can implement the in-order traversal in Java as well.
1
2java
3class Solution {
4 private TreeNode previousNode = null; // Initialize predecessor with null
5 private int minimumDifference = Integer.MAX_VALUE; // Initialize result with maximum value
6
7 public int minDiffInBST(TreeNode root) {
8 if (root == null) // if root node is null, return 0
9 return 0;
10 inOrder(root); // else start process from root
11 return minimumDifference; // return result
12 }
13 public void inOrder(TreeNode root) {
14 if (root == null) // if current node is null, return
15 return;
16 inOrder(root.left); // recursive call to left node
17 if (previousNode != null) // if predecessor is not null, calculate minimum difference
18 minimumDifference = Math.min(minimumDifference, root.val - previousNode.val);
19 previousNode = root; // update predecessor with current node
20 inOrder(root.right); // recursive call to right node
21 }
22}
JavaScript Solution
1
2javascript
3var minDiffInBST = function(root) {
4 var min = Number.MAX_SAFE_INTEGER; // Initialize result with maximum integer
5 var pre = -1; // Initialize predecessor with -1
6 var inOrder = function(root){ // start with root node
7 if(root === null) // if node is null, return
8 return;
9 inOrder(root.left); // recursive call to left node
10 if(pre >= 0) // if predecessor is not null, calculate minimum difference
11 min = Math.min(min, root.val - pre);
12 pre = root.val; // update predecessor with current node
13 inOrder(root.right); //recursive call to right node
14 }
15 inOrder(root); //begin traversal from root
16 return min; // return result
17};
In all cases, we compare the current node with its immediate predecessor in the in-order sequence to compute the minimum difference. This approach significantly reduces the workload by eliminating the need to compare every pair of nodes. Implementing this solution requires an understanding of Binary Search Tree properties and in-order traversal.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.