algoadvance

Leetcode 783. Minimum Distance Between BST Nodes

Problem Statement

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

Clarifying Questions

1. Input Constraints:
   • What is the range of values for the tree nodes?
   • What is the maximum number of nodes in the BST?
2. Output Constraints:
   • Should the function return an integer value representing the minimum difference?
3. Tree Specifics:
   • Can the tree contain duplicate values?
   • Is it guaranteed that the tree is a valid BST?

Strategy

1. Inorder Traversal:
   • Perform an inorder traversal of the BST. Since inorder traversal of a BST results in a sorted sequence of values, the minimum difference will always be found between consecutive nodes in this sequence.
2. Comparing Adjacent Nodes:
   • As we traverse the tree, we maintain a variable to store the previous node value and update the minimum difference based on the current node and the previous node.
3. Edge Cases:
   • If the tree has only one node, we return an appropriate value indicating insufficient nodes to compare.

Code

#include <climits> // For INT_MAX
#include <algorithm> // For std::min

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int minDiffInBST(TreeNode* root) {
        int minDiff = INT_MAX;
        int prev = -1; // Initialize prev with a value that won't be in the BST (assuming BST values are positive).

        // Helper function for inorder traversal
        void inorder(TreeNode* node) {
            if (!node) return;
            inorder(node->left);
            if (prev != -1) { // If prev has been updated at least once
                minDiff = std::min(minDiff, node->val - prev);
            }
            prev = node->val;
            inorder(node->right);
        }
        
        inorder(root);
        return minDiff;
    }
};

Time Complexity

• Time Complexity: O(N), where N is the number of nodes in the BST. This is because we have to traverse all the nodes in the BST.
• Space Complexity: O(H), where H is the height of the tree, which can be O(log N) for a balanced tree and O(N) for a skewed tree. This space is used by the recursion stack.

This approach ensures we correctly find the minimum distance between any two nodes in the BST by leveraging properties of inorder traversal resulting in a sorted sequence.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?