easy Minimum Difference Between BST Nodes

Problem Statement

Given a Binary Search Tree (BST), you are required to find the smallest difference between the values of any two different nodes.

In a BST, the nodes are arranged in a manner where the value of nodes on the left is less than or equal to the root, and the value of nodes on the right is greater than the root.

Example

Example 1:

• Input:

    4
   / \
  2   6
 / \
1   3

• Expected Output: 1
• Justification: The pairs (1,2), (2,3), or (3,4) have the smallest difference of 1.

Example 2:

• Input:

    10
   /  \
  5   15
 / \    \
2   7    18

• Expected Output: 2
• Justification: The pair (5,7) has the smallest difference of 2.

Example 3:

• Input:

  40
   \
    70
   /  \
  50  90

• Expected Output: 10
• Justification: The pair (40,50) has the smallest difference of 10.

Constraints:

• The number of nodes in the tree is in the range [2, 10⁴].
• 0 <= Node.val <= 10⁵

Solution

A binary search tree has an interesting property where if you perform an in-order traversal, the result is a list of numbers in ascending order.

To solve this problem, you'll first perform an in-order traversal of the Binary Search Tree (BST) and store elements in the array. Once the traversal is complete and the list is fully populated, the next step is to find the minimum difference between adjacent elements in this list. Since the list is sorted, the smallest difference between any two nodes in the BST will be among these adjacent pairs.

1. In-Order Traversal: Start with the root of the tree and traverse the tree in in-order (left, root, right). This will give us the nodes in ascending order.

2. Calculate Minimum Difference: Once the in-order traversal is done and we have the values in ascending order, iterate through the list and calculate the difference between each pair of adjacent nodes.

3. Return the Minimum: Return the smallest difference.

Algorithm Walkthrough:

For the tree:

    4
   / \
  2   6
 / \
1   3

• Perform in-order traversal: Resulting list is [1, 2, 3, 4, 6]
• Calculate the differences: 1 (between 1 & 2), 1 (between 2 & 3), 1 (between 3 & 4), and 2 (between 4 & 6).
• The smallest difference is 1.

Here is the visual representation of the algorithm:

Code

Here is the code for this algorithm:

import java.util.ArrayList;
import java.util.List;

// TreeNode class to represent the Binary Search Tree nodes.
// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode(int x) { val = x; }
// }

public class Solution {

  // Using a List to hold the values in order.
  private List<Integer> nodes = new ArrayList<>();

  public int minDiffInBST(TreeNode root) {
    nodes.clear(); // make sure nodes is empty

    // First, perform the in-order traversal.
    inorderTraversal(root);

    // Initialize the minimum difference to the largest possible value.
    int minDiff = Integer.MAX_VALUE;

    // Loop through the list and find the difference between each consecutive pair.
    for (int i = 1; i < nodes.size(); i++) {
      minDiff = Math.min(minDiff, nodes.get(i) - nodes.get(i - 1));
    }

    return minDiff;
  }

  // Helper method to perform the in-order traversal.
  private void inorderTraversal(TreeNode node) {
    if (node == null) return;
    inorderTraversal(node.left); // Recursively visit the left subtree.
    nodes.add(node.val); // Add the current node's value.
    inorderTraversal(node.right); // Recursively visit the right subtree.
  }

  public static void main(String[] args) {
    // First test case
    TreeNode example1 = new TreeNode(4);
    example1.left = new TreeNode(2);
    example1.left.left = new TreeNode(1);
    example1.left.right = new TreeNode(3);
    example1.right = new TreeNode(6);

    // Second test case
    TreeNode example2 = new TreeNode(40);
    example2.right = new TreeNode(70);
    example2.right.left = new TreeNode(50);
    example2.right.right = new TreeNode(90);

    Solution solution = new Solution();

    System.out.println(solution.minDiffInBST(example1)); // Expected output: 1
    System.out.println(solution.minDiffInBST(example2)); // Expected output: 10 (40-50)
  }
}

Complexity Analysis

Time Complexity

1. In-order Traversal (inorderTraversal):

   • The algorithm performs an in-order traversal of the binary search tree (BST).
   • Each node is visited exactly once, and there are n nodes in the tree.
   • Therefore, the time complexity for the in-order traversal is .

2. Calculating Minimum Difference:

   • After the in-order traversal, the algorithm loops through the list of nodes to calculate the minimum difference between consecutive elements.
   • The list will have n elements, and the algorithm performs a single pass through the list.
   • Therefore, the time complexity for this step is also .

Combining these steps, the overall time complexity of the algorithm is .

Space Complexity

1. Space for the List (nodes):

   • The list nodes stores the values of all the nodes in the BST. Since there are n nodes in the tree, the space used by the list is .

2. Recursive Stack Space:

   • The in-order traversal uses recursion, which requires stack space proportional to the height of the tree.
   • In the worst case (a skewed tree), the height of the tree will be n, resulting in a space complexity of for the recursion stack.
   • In the best case (a balanced tree), the height of the tree will be .