783. Minimum Distance Between BST Nodes

EasyTreeDepth-First SearchBreadth-First SearchBinary Search TreeBinary Tree
Leetcode Link

Problem Description

The task is to find the minimum difference (also known as the minimum absolute difference) between the values of any two different nodes in a Binary Search Tree (BST). Remember, a BST has the property that all left descendants of a node have values less than the node's value, and all right descendants have values greater than the node's value. This property can be utilized to find the minimum difference in an efficient way.

Intuition

To solve this problem, we need to consider the properties of a BST and how they can help in finding the minimum difference. In a BST, an in-order traversal results in a sorted sequence of values. The smallest difference between any two nodes is likely to be between two adjacent nodes in this sorted order. So, the solution involves performing an in-order traversal of the tree.

The solution uses a recursive depth-first search (DFS) strategy to perform the in-order traversal. During the traversal:

  1. Visit the left subtree.
  2. Process the current node:
    • Compare the current nodeโ€™s value with the value of the previous node (which is the closest smaller value since we are doing in-order traversal).
    • Update the minimum difference (ans) if the current difference is less than the previously recorded minimum difference.
  3. Visit the right subtree.

The nonlocal keyword is used for the variables ans and prev inside the dfs helper function to update their values across recursive calls. This is necessary because ans keeps track of the current minimum difference we have found, and prev keeps track of the last node's value we visited.

Initially, we set ans to infinity (inf in Python) to ensure any valid difference found will be smaller and thus update ans. The prev variable is initialized to infinity as well since we have not encountered any nodes before the traversal. The algorithm starts by calling the dfs helper function with the root of the BST, which then recursively performs the in-order traversal and updates ans with the minimum difference that it finds.

By the time we are done with the in-order traversal, ans holds the minimum difference between any two nodes in the BST, and we return it as the result.

Learn more about Tree, Depth-First Search, Breadth-First Search, Binary Search Tree and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which technique can we use to find the middle of a linked list?

Solution Approach

The implementation of the solution is based on a Depth-First Search (DFS) algorithm performing an in-order traversal of the Binary Search Tree (BST). A traversal is in-order if it visits the left child, then the node itself, and then the right child recursively. This approach leverages the BST's property that an in-order traversal results in a sorted sequence of node values.

Here are the steps in the algorithm, along with how each is implemented in the solution:

  1. Depth-First Search (DFS):

    • A recursive method dfs(root) is defined, where root is the current node in the traversal. If root is None, the function returns immediately, as there's nothing to process (base case for the recursion).
    • The dfs function is called with the left child of the current node, dfs(root.left), to traverse the left subtree first.

  2. Processing Current Node:

    • Once we are at the leftmost node, which has no left child, the processing of nodes begins.
    • The current node's value is compared with the last node's value stored in the variable prev (initialized at infinity to start with). The difference is calculated as abs(prev - root.val).

  3. Updating Minimum Difference:

    • A nonlocal variable ans is used to keep track of the minimum difference encountered throughout the traversal. If the current difference is less than ans, we update ans with this new minimum.
    • The variable prev is updated with the current node's value, root.val, to ensure it's always set to the value of the last node visited.

  4. Recursive Right Subtree Traversal:

    • After processing the current node, the function calls itself with the right child of the current node, dfs(root.right), thus exploring the right subtree.

  5. Result:

    • Once the entire tree has been traversed, the ans variable will hold the smallest difference found between any two nodes.

The use of the nonlocal keyword is key here, as ans and prev are updated by the recursive calls within the dfs function, and their values need to be retained across those calls.

A Python class named Solution contains the method minDiffInBST which initiates the DFS with the first call to dfs(root). The inf value is imported from Python's math module and represents infinity, used for comparison purposes to ensure the actual difference always replaces the initial value.

The ans is initialized with inf so that the first computed difference (which will be finite) will become the new minimum. The prev variable is also initialized outside the dfs function to inf in order to manage the case when the first node (the smallest value in the BST) has no predecessor.

Data Structure: The recursive stack is the implicit data structure used here for the DFS implementation. No additional data structures are needed since the problem can be solved with the traversal alone.

Considering the algorithm and pattern applied, the solution efficiently finds and returns the minimum absolute difference between any two nodes in the BST by leveraging its properties and an in-order DFS.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used in a depth first search?

Example Walkthrough

Let's say we have a Binary Search Tree (BST) with the following structure:

1    4
2   / \
3  2   6
4 / \
51   3

  1. We initiate a Depth-First Search (DFS) from the root of the BST, which is the node with value 4.

  2. The DFS will first go to the left subtree (value 2). Since 2 also has a left child, the DFS will go further left, reaching all the way to node 1, which is the leftmost node and has no children.

  3. Node 1 is processed, and since it's the first node, there's no previous node to compare with, so prev is set to this node's value (1). The ans is still infinity at this point.

  4. The DFS backtracks to node 2, and 2 is compared with the previous node 1. The absolute difference is 2 - 1 = 1, which is less than infinity, so ans is updated to 1. Prev is now updated to 2.

  5. The DFS then moves to the right child of node 2, which is node 3. The difference between 3 and the previous node 2 is 3 - 2 = 1. Since ans is already 1, it does not get updated.

  6. DFS backtracks to the root node 4, but we've already processed its left subtree. Now, we compare 4 with the previous node 3. The absolute difference is 4 - 3 = 1, which is the same as ans, so no update to ans is made. Prev is updated to 4.

  7. The DFS proceeds to the right child of root, node 6. We calculate the difference between the previous node 4 and 6, giving us 6 - 4 = 2, which is greater than ans. Thus, no update is made.

  8. The traversal ends as there are no more nodes to visit. Our minimum difference ans is 1, which is the minimum absolute difference between any two nodes in this BST.

The process concludes by returning 1 as the minimum difference between the values of any two different nodes in the BST.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3     def __init__(self, val=0, left=None, right=None):
4         self.val = val
5         self.left = left
6         self.right = right
7
8class Solution:
9    def minDiffInBST(self, root: TreeNode) -> int:
10        # Helper function for depth-first search traversal of the binary tree
11        def in_order_traversal(node):
12            if node is None:
13                return
14          
15            # Traverse the left subtree
16            in_order_traversal(node.left)
17          
18            # Process the current node
19            # Update the smallest difference and the previous value
20            nonlocal min_difference, previous_value
21            min_difference = min(min_difference, node.val - previous_value)
22            previous_value = node.val
23          
24            # Traverse the right subtree
25            in_order_traversal(node.right)
26
27        # Initialize the minimum difference as infinity
28        # The prev variable is used to keep track of the previous node's value
29        # Because the initial "previous value" is not defined, we use infinity
30        min_difference, previous_value = float('inf'), float('-inf')
31      
32        # Call the helper function to start in-order traversal from the root
33        in_order_traversal(root)
34      
35        # Return the minimum difference found
36        return min_difference
37
1// Definition for a binary tree node.
2class TreeNode {
3    int val;
4    TreeNode left;
5    TreeNode right;
6    TreeNode() {}
7    TreeNode(int val) { this.val = val; }
8    TreeNode(int val, TreeNode left, TreeNode right) {
9        this.val = val;
10        this.left = left;
11        this.right = right;
12    }
13}
14
15class Solution {
16    // Variable to store the minimum difference
17    private int minDifference;
18    // Variable to keep track of the previously visited node's value in in-order traversal
19    private int prevValue;
20    // A large value to initialize minDifference and prevValue. It signifies "infinity".
21    private final int INF = Integer.MAX_VALUE;
22
23    // Public method to find the minimum difference between values of any two nodes in a BST
24    public int minDiffInBST(TreeNode root) {
25        // Initialize minDifference to "infinity" as we look for the minimum value
26        minDifference = INF;
27        // Initialize prevValue to "infinity" to handle the edge case of the first node
28        prevValue = INF;
29        // Call the helper method to do a depth-first search starting from the root
30        dfs(root);
31        // Return the minimum difference found
32        return minDifference;
33    }
34
35    // Helper method to perform in-order traversal and find the minimum difference
36    private void dfs(TreeNode node) {
37        // Base case: if the node is null, just return
38        if (node == null) {
39            return;
40        }
41        // Recursively call dfs for the left subtree to visit nodes in in-order
42        dfs(node.left);
43        // Update the minimum difference with the smallest difference found so far
44        // between the current node's value and the previous node's value
45        minDifference = Math.min(minDifference, Math.abs(node.val - prevValue));
46        // Update the prevValue to the current node's value for subsequent iterations
47        prevValue = node.val;
48        // Recursively call dfs for the right subtree to continue in-order traversal
49        dfs(node.right);
50    }
51}
52
1#include <algorithm>  // Include algorithm header for std::min function
2
3// Definition for a binary tree node.
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8    TreeNode() : val(0), left(nullptr), right(nullptr) {}
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15    // Initialize the maximum possible value for an integer as infinity.
16    // This will be used to calculate the minimum difference.
17    static const int INF = INT_MAX;
18
19    // Variable to hold the current minimum difference found in the BST.
20    int minDifference;
21
22    // Variable to keep track of the previous node's value during in-order traversal.
23    int previousValue;
24
25    // Constructor initializes member variables.
26    Solution() : minDifference(INF), previousValue(-INF) {}
27
28    // Function to find the minimum difference between any two nodes in the BST.
29    int minDiffInBST(TreeNode* root) {
30        // Reset the minDifference and previousValue before reusing the solution instance.
31        minDifference = INF;
32        previousValue = -INF;
33        // Start the depth-first search (in-order traversal) of the tree.
34        inOrderTraversal(root);
35        // After the traversal, minDifference will hold the minimum difference.
36        return minDifference;
37    }
38
39    // Helper function to perform in-order traversal on the BST and
40    // compute the minimum difference.
41    void inOrderTraversal(TreeNode* node) {
42        // If the node is null, return immediately.
43        if (!node) return;
44
45        // Traverse the left subtree first.
46        inOrderTraversal(node->left);
47
48        // If previousValue is not set to the initial value (which is -INF here),
49        // update the minDifference with the minimum of current minDifference and
50        // the difference between the current node's value and previousValue.
51        if (previousValue != -INF) {
52            minDifference = std::min(minDifference, abs(node->val - previousValue));
53        }
54        // Update previousValue to hold the current node's value for the next comparison.
55        previousValue = node->val;
56
57        // Traverse the right subtree.
58        inOrderTraversal(node->right);
59    }
60};
61
1// Definition for a binary tree node.
2class TreeNode {
3  val: number;
4  left: TreeNode | null;
5  right: TreeNode | null;
6
7  constructor(val: number = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
8    this.val = val;
9    this.left = left;
10    this.right = right;
11  }
12}
13
14// The maximum possible value for a number in JavaScript.
15const INFINITY = Number.MAX_SAFE_INTEGER;
16
17// Variable to hold the current minimum difference found in the BST.
18let minDifference: number;
19
20// Variable to keep track of the previous node's value during in-order traversal.
21let previousValue: number;
22
23// Function to find the minimum difference between any two nodes in the BST.
24// Note that we don't have to reset minDifference and previousValue here
25// because they're not part of a class instance anymore.
26function minDiffInBST(root: TreeNode | null): number {
27  // Initialize minDifference and previousValue for a new computation.
28  minDifference = INFINITY;
29  previousValue = -INFINITY;
30
31  // Start the depth-first search (in-order traversal) of the tree.
32  inOrderTraversal(root);
33
34  // After the traversal, minDifference will hold the minimum difference.
35  return minDifference;
36}
37
38// Helper function to perform in-order traversal on the BST and
39// compute the minimum difference.
40function inOrderTraversal(node: TreeNode | null) {
41  // If the node is null, return immediately.
42  if (node === null) return;
43
44  // Traverse the left subtree first.
45  inOrderTraversal(node.left);
46
47  // If previousValue is not set to the initial value (which is -INFINITY here),
48  // update the minDifference with the minimum of current minDifference and
49  // the difference between the current node's value and previousValue.
50  if (previousValue !== -INFINITY) {
51    minDifference = Math.min(minDifference, Math.abs(node.val - previousValue));
52  }
53
54  // Update previousValue to hold the current node's value for the next comparison.
55  previousValue = node.val;
56
57  // Traverse the right subtree.
58  inOrderTraversal(node.right);
59}
60
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Time and Space Complexity

The given code performs an in-order traversal of a binary search tree (BST) to find the minimum difference between any two nodes. Here's the analysis of its complexity:

  • Time Complexity: The time complexity of the function is O(n), where n is the number of nodes in the BST. This is because the in-order traversal visits each node exactly once.

  • Space Complexity: The space complexity of the recursive in-order traversal is O(h), where h is the height of the BST. This accounts for the call stack during the recursive calls. In the worst case of a skewed BST, the height h can become n, which would make the space complexity O(n). In a balanced BST, however, the space complexity would be O(log n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ