#783

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Minimum Distance Between BST Nodes

Find the minimum difference between values of two different nodes in a Binary Search Tree using tree traversal and state tracking.

tree depth first search breadth first search binary search tree binary tree

Problem Statement

You are given the root of a Binary Search Tree (BST). Your task is to return the minimum absolute difference between the values of any two distinct nodes in the tree. A Binary Search Tree is a tree where for each node, the left subtree's values are smaller, and the right subtree's values are larger.

To solve this problem, you should focus on traversing the tree in a way that allows you to track the smallest difference between node values. An optimal solution requires utilizing in-order traversal, which guarantees that the nodes are processed in ascending order.

Examples

Example 1

Input: root = [4,2,6,1,3]

Output: 1

Example details omitted.

Example 2

Input: root = [1,0,48,null,null,12,49]

Output: 1

Example details omitted.

Constraints

The number of nodes in the tree is in the range [2, 100].
0 <= Node.val <= 105

Solution Approach

In-Order Traversal with State Tracking

The key to solving this problem efficiently is performing an in-order traversal of the BST. During the traversal, track the previous node's value and calculate the difference between the current node and the previous node. This ensures that the minimum difference is found during the traversal without needing to compare every pair of nodes.

Minimizing the Difference in Real-Time

As you traverse the BST, continuously update a variable to store the minimum difference encountered. This way, you avoid comparing all pairs of nodes after traversal, thus optimizing performance. The solution depends on the observation that the minimum difference will occur between consecutive nodes in an in-order traversal.

Optimized Time and Space Complexity

The in-order traversal ensures that each node is processed exactly once, yielding a time complexity of O(n), where n is the number of nodes in the tree. Since we are only storing a few variables (the previous node value and the minimum difference), the space complexity is O(h), where h is the height of the tree (or the stack depth in a recursive solution).

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) because each node is visited once during the in-order traversal. The space complexity is O(h), where h is the height of the tree, representing the space needed for the recursion stack. In the worst case (for unbalanced trees), h can be equal to n, while in a balanced tree, h would be log(n).

What Interviewers Usually Probe

Look for the candidate's understanding of tree traversal techniques, especially in-order traversal.
Ensure the candidate is aware of optimizing the algorithm to minimize unnecessary comparisons.
Check if the candidate can explain how space complexity relates to the recursive depth of the solution.

Common Pitfalls or Variants

Common pitfalls

Failing to recognize that in-order traversal of a BST visits nodes in sorted order.
Not optimizing the space complexity when using recursion by improperly handling deep recursion in unbalanced trees.
Attempting to compare all pairs of nodes, leading to a brute-force O(n^2) solution.

Follow-up variants

Consider solving the problem iteratively, using a stack to simulate the recursion.
Modify the problem to find the minimum difference in a Binary Tree instead of a Binary Search Tree.
Extend the problem to find the k-th smallest element and its nearest neighbor in a BST.

FAQ

What is the Minimum Distance Between BST Nodes problem about?

The problem asks to find the minimum absolute difference between the values of any two distinct nodes in a Binary Search Tree using tree traversal and state tracking.

How do I solve Minimum Distance Between BST Nodes efficiently?

You can solve the problem efficiently using an in-order traversal of the BST while tracking the minimum difference between consecutive nodes.

What traversal method should I use for this problem?

In-order traversal is ideal because it processes the nodes in ascending order, allowing easy calculation of the minimum difference between consecutive nodes.

What is the time complexity of the optimal solution?

The time complexity of the optimal solution is O(n), where n is the number of nodes in the tree, as each node is visited once during the traversal.

Can I improve the space complexity of the solution?

Yes, you can optimize the space complexity by using an iterative in-order traversal to avoid recursion stack overhead, especially for unbalanced trees.

terminal

Solution

Solution 1: Inorder Traversal

The problem requires us to find the minimum difference between the values of any two nodes. Since the inorder traversal of a binary search tree is an increasing sequence, we only need to find the minimum difference between the values of two adjacent nodes in the inorder traversal.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDiffInBST(self, root: Optional[TreeNode]) -> int:
        def dfs(root: Optional[TreeNode]):
            if root is None:
                return
            dfs(root.left)
            nonlocal pre, ans
            ans = min(ans, root.val - pre)
            pre = root.val
            dfs(root.right)

        pre = -inf
        ans = inf
        dfs(root)
        return ans

Continue Practicing

#653 two sum iv input is a bst #530 minimum absolute difference in bst #449 serialize and deserialize bst