Solution: Minimum Difference Between BST Nodes

Grokking Data Structures & Algorithms for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Minimum Difference Between BST Nodes

Table of Contents

Contents are not accessible

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:

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:

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<sup>4</sup>].
0 <= Node.val <= 10<sup>5</sup>

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.

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.
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.
Return the Minimum: Return the smallest difference.

Algorithm Walkthrough:

For the tree:

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:

Min Diff between BST nodes

Code

Here is the code for this algorithm:

Python3

. . . .

Complexity Analysis

Time Complexity

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 $O(n)$ .
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 $O(n)$ .

Combining these steps, the overall time complexity of the algorithm is $O(n)$ .

Space Complexity

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 $O(n)$ .
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 $O(n)$ for the recursion stack.
- In the best case (a balanced tree), the height of the tree will be $O(log n)$ .

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible