Minimum Distance Between Bst Nodes

Solution For Minimum Distance Between Bst Nodes

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.

Solution:

Approach:

The idea here is to traverse the BST in in-order, which will give us a sorted sequence. While traversing the in-order sequence, we can keep track of the minimum difference between adjacent nodes.

Algorithm:

  1. Initialize a variable called min_diff to infinity.
  2. Initialize a variable called prev_val to null.
  3. Traverse the BST in in-order.
  4. For each node, calculate the absolute difference between its value and the prev_val variable. If this absolute difference is less than min_diff, update min_diff to this value.
  5. Update prev_val to the current node’s value.
  6. Return the final value of min_diff.

Code:

Here is the code implementation of the above algorithm in Python:

“`
class Solution:
def minDiffInBST(self, root: TreeNode) -> int:
# Initialize min_diff to infinity
min_diff = float(“inf”)
# Initialize prev_val to null
prev_val = None

    # Define a recursive function to traverse the BST in in-order
    def traverse(node):
        nonlocal min_diff, prev_val
        # Base case: if node is null, return
        if not node:
            return
        # Traverse left subtree
        traverse(node.left)
        # Check the difference between current node's value and prev_val
        if prev_val is not None:
            diff = abs(node.val - prev_val)
            if diff < min_diff:
                min_diff = diff
        # Update prev_val to current node's value
        prev_val = node.val
        # Traverse right subtree
        traverse(node.right)

    # Call the recursive function on the root node
    traverse(root)

    # Return the final value of min_diff
    return min_diff

“`

Time Complexity:

The time complexity of this algorithm is O(N), where N is the number of nodes in the BST. This is because we traverse each node exactly once.

Space Complexity:

The space complexity of this algorithm is O(H), where H is the height of the BST. This is because we use a recursive function to traverse the BST, and the maximum depth of the recursive call stack is equal to the height of the BST.

Step by Step Implementation For Minimum Distance Between Bst Nodes

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDiffInBST(TreeNode root) {
        // Base case
        if (root == null) {
            return 0;
        }
        
        // Recursive case 1: If the root has no left child, 
        // then the minimum difference must be between the root and its right child's value
        if (root.left == null) {
            return minDiffInBST(root.right);
        }
        
        // Recursive case 2: If the root has no right child, 
        // then the minimum difference must be between the root and its left child's value
        if (root.right == null) {
            return minDiffInBST(root.left);
        }
        
        // Recursive case 3: If the root has both left and right children, 
        // then the minimum difference must be either between the root and its left child's value 
        // or between the root and its right child's value, whichever is smaller
        return Math.min(minDiffInBST(root.left), minDiffInBST(root.right));
    }
}
This problem can be solved by doing a level-order traversal of the BST. We can keep track of the previous node at each level, and calculate the minimum distance between the current node and the previous node.
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDiffInBST = function(root) {
    // your code here
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minDiffInBST(TreeNode* root) {
        int minDiff = INT_MAX;
        stack stk;
        TreeNode* cur = root;
        TreeNode* prev = NULL;
        while (!stk.empty() || cur) {
            while (cur) {
                stk.push(cur);
                cur = cur->left;
            }
            cur = stk.top();
            stk.pop();
            if (prev) {
                minDiff = min(minDiff, abs(prev->val - cur->val));
            }
            prev = cur;
            cur = cur->right;
        }
        return minDiff;
    }
};
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int MinDiffInBST(TreeNode root) {
        //inorder traversal of BST gives us sorted array
        List inorder = new List();
        InOrder(root, inorder);
        
        //minimum difference will be between adjacent elements in sorted array
        int minDiff = int.MaxValue;
        for(int i = 0; i < inorder.Count - 1; i++){
            minDiff = Math.Min(minDiff, inorder[i+1] - inorder[i]);
        }
        
        return minDiff;
    }
    
    public void InOrder(TreeNode root, List inorder){
        if(root == null) return;
        
        InOrder(root.left, inorder);
        inorder.Add(root.val);
        InOrder(root.right, inorder);
    }
}


Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]