Closest in BST – Find the Minimum Absolute Difference in C#

1. Introduction

A Binary Search Tree (BST) is a special type of binary tree in which each node follows a specific ordering rule.

In this problem, we are given:

• The root node of a Binary Search Tree.
• An integer k.

Our task is to find the minimum absolute difference between k and the value of any node in the BST.

In simple words, we need to find the node whose value is closest to the given integer k.

Example:

Input:
root = [10, 2, 11, 1, 5, N, N, N, N, 3, 6, N, 4]
k = 13

Output:
2

Explanation:

The closest node value to 13 is 11.

|11 - 13| = 2

Therefore, the answer is 2.

2. Understanding the Binary Search Tree

Before solving the problem, we should understand the BST property.

A Binary Search Tree follows three important rules:

1. All values in the left subtree are smaller than the root.
2. All values in the right subtree are greater than the root.
3. Both left and right subtrees must also follow BST rules.

Example:

          10
         /  \
        5    15
       / \   / \
      2   7 12  20

If we want to search for the value 12:

• Start from 10.
• Since 12 is greater than 10, move right.
• Reach 15.
• Since 12 is smaller than 15, move left.
• Reach 12.

We can use the same searching logic to solve the Closest in BST problem.

3. Approach – Using BST Property

Instead of visiting every node, we can use the BST property to eliminate unnecessary searches.

Algorithm:

1. Initialize minDifference with int.MaxValue.
2. Start traversing from the root.
3. Calculate the absolute difference between the current node value and k.
4. Compare the current difference with minDifference.
5. Update minDifference if the current difference is smaller.
6. If the difference is zero, return zero immediately.
7. If k is smaller than the current node value, move to the left child.
8. Otherwise, move to the right child.
9. Continue until the current node becomes null.
10. Return the minimum difference.

4. C# Implementation

class Solution {
    public int minDiff(Node root, int k) {

        int minDifference = int.MaxValue;

        while (root != null) {

            int diff = Math.Abs(root.data - k);

            minDifference = Math.Min(minDifference, diff);

            // Exact match found
            if (diff == 0) {
                return 0;
            }

            // Search in the left subtree
            if (k < root.data) {
                root = root.left;
            }

            // Search in the right subtree
            else {
                root = root.right;
            }
        }

        return minDifference;
    }
}

5. Explaining the Code Line by Line

Step 1: Initialize minimum difference

int minDifference = int.MaxValue;

We initialize the minimum difference with the maximum possible integer value.

Why?

Because we need to compare every visited node's difference and find the smallest one.

Step 2: Traverse the BST

while (root != null)

We continue traversing until there are no more nodes to visit in the selected search path.

Step 3: Calculate absolute difference

int diff = Math.Abs(root.data - k);

Math.Abs() returns the positive difference between two numbers.

Example:

root.data = 10;
k = 13;

diff = Math.Abs(10 - 13);

// Result: 3

Step 4: Update the minimum difference

minDifference = Math.Min(minDifference, diff);

Math.Min() returns the smaller of the two values.

For example:

Current minimum = 3
New difference  = 2

Updated minimum = 2

Step 5: Check for an exact match

if (diff == 0) {
    return 0;
}

If the current node value is equal to k, the difference is zero.