530. Minimum Absolute Difference in BST

EasyTreeDepth-First SearchBreadth-First SearchBinary Search TreeBinary Tree

Problem Description

This LeetCode problem asks us to find the minimum absolute difference between the values of any two different nodes in a Binary Search Tree (BST). A BST is a tree data structure where each node has at most two children, referred to as the left child and the right child. For any node in a BST, the value of all the nodes in the left subtree are less than the node's value, and the value of all the nodes in the right subtree are greater than the node's value.

The "minimum absolute difference" refers to the smallest difference in value between any pair of nodes in the tree. An important characteristic of a BST is that when it is traversed in-order (left node, current node, right node), it will yield the values in a sorted manner. This property will be crucial for finding the minimum absolute difference without having to compare every pair of nodes in the tree.

Flowchart Walkthrough

Let's use the provided algorithm flowchart to determine the appropriate algorithm for solving LeetCode 530, Minimum Absolute Difference in BST. Here's a detailed analysis:

Is it a graph?

Yes: A Binary Search Tree (BST) is a type of graph, specifically a tree.

Is it a tree?

Yes: Since a BST is inherently a tree, we continue along the tree path.

Is the problem related to directed acyclic graphs (DAGs)?

No: Although a tree is technically a DAG, the essence of this problem does not involve typical DAG operations like topological sorting.

Is the problem related to shortest paths?

No: We are asked to find the minimum absolute difference between values, not pathways.

Does the problem involve connectivity?

No: The issue at hand deals specifically with value differences, not connectivity.

Is the graph weighted?

No: The problem does not involve weighted calculations between nodes, only simple comparisons.

By following the "Is it a tree?" -> "Yes" -> "DFS" path, the flowchart guides us to use DFS (Depth-First Search) as the technique to tackle this problem. This method is suitable due to the tree structure of the BST, enabling efficient traversal and comparison of node values for determining minimum differences.

In conclusion, Depth-First Search is the appropriate method as suggested by analyzing the problem through the flowchart.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To arrive at the solution, we leverage the in-order traversal property of the BST mentioned above. The idea is to perform an in-order traversal of the BST, which effectively means we will be processing the nodes in ascending order of their values.

During the traversal, we keep track of the value of the previously processed node.
At each current node, we calculate the absolute difference between the current node's value and the previously visited node's value.
We keep an ongoing count of the minimum absolute difference encountered so far.
By the end of the traversal, the minimum absolute difference will have been found.

The intuition behind this approach is based on the fact that the smallest difference between any two values in a sorted list is always between adjacent values. Since an in-order traversal of a BST gives us a sorted list of values, we only need to check adjacent nodes to determine the minimum absolute difference in the entire tree.

We use a helper function dfs (Depth-First Search) that performs the in-order traversal recursively. The nonlocal keyword is used to update the ans and prev variables defined in the outer scope of the dfs function.

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

Solution Approach

The provided Python solution makes use of recursion to implement the in-order traversal pattern for navigating the BST. Here's a step by step breakdown of how the implementation works:

A nested function named dfs (short for "Depth-First Search") is defined within the getMinimumDifference method. This dfs function is responsible for performing the in-order traversal of the BST.
The dfs function does nothing if it encounters a None node (the base case of the recursion), which means that it has reached a leaf node's child.
When the dfs function visits a node, it first recursively calls itself on the left child of the current node to ensure that the nodes are visited in ascending order.
After visiting the left child, the function then processes the current node by calculating the absolute difference between the current node's value and the previously visited node's value, and keeps track of this absolute difference if it's the smallest one seen so far. This is done using the ans variable, which is initialized with infinity (inf). ans represents the minimum absolute difference found during the traversal.
The prev variable holds the value of the previously visited node in the traversal. Initially, prev is also initialized with inf, and it is updated to the current node's value before moving to the right child.
Once the current node has been processed, the dfs function recursively calls itself on the right child to complete the in-order visitation pattern.
The nonlocal keyword is used for ans and prev to allow the nested dfs function to modify these variables that are defined in the enclosing getMinimumDifference method's scope.
The getMinimumDifference method initializes ans and prev with inf and begins the in-order traversal by calling the dfs function on the root node of the BST.
After the in-order traversal is complete, ans holds the minimum absolute difference between the values of any two nodes in the BST. This value is returned as the final result.

Through the use of in-order traversal, the algorithm ensures that each node is compared only with its immediate predecessor in terms of value, resulting in an efficient way to find the minimum absolute difference.

Here's the algorithm represented in pseudocode:

    def in_order_traversal(node):
        if node is not None:
            in_order_traversal(node.left)
            process(node)
            in_order_traversal(node.right)
  
    def process(node):
        update_minimum_difference(previous_node_value, node.value)
        previous_node_value = node.value

In the pseudocode, process(node) represents the steps of comparing the current node's value with the previous node's value and updating the minimum difference accordingly.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider the following BST for this example:

Let's apply the in-order traversal to this BST and keep track of the previous node to calculate the differences and find the minimum absolute difference.

Start at the root (4), then traverse to the left child (2). Since 2 has a left child (1), continue traversing left until reaching a leaf node.
Process node 1: This is the first node, so there's no previous node to compare with. Set prev to 1.
Traverse up and to the right, now to node 2. Calculate the absolute difference with prev: |2 - 1| = 1, and since prev was set to 1 earlier, set ans to 1 (this is our first comparison, so it's also the smallest so far). Update prev to 2.
Process node 2: Node 2 is considered again, but the comparison has already been made with its left side. No left child traversal needed now.
Traverse to the right child of node 2, which is node 3. Calculate the absolute difference with prev: |3 - 2| = 1. Since ans is already 1 and |3 - 2| is also 1, ans remains unchanged. Update prev to 3.
Move up to node 4, the root. Calculate the absolute difference with prev: |4 - 3| = 1. The ans is still 1, so there's no change. Update prev to 4.
Finally, move to the right child of the root, which is node 6. Calculate the absolute difference with prev: |6 - 4| = 2. Since ans is 1, and |6 - 4| is greater than 1, there's no change to ans.

By the end of the traversal, ans holds the value of 1, which is the minimum absolute difference that was found between the values of adjacent nodes during the in-order traversal of the BST. Therefore, the minimum absolute difference between any two nodes in this BST is 1.

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 getMinimumDifference(self, root: TreeNode) -> int:
10        # Initialize the minimum difference and previous node value
11        self.min_diff = float('inf')
12        self.prev_val = -float('inf')
13
14        # Depth-First Search In-Order Traversal
15        def in_order_traverse(node):
16            if not node:
17                return
18          
19            # Traverse the left subtree
20            in_order_traverse(node.left)
21          
22            # Update the minimum difference
23            self.min_diff = min(self.min_diff, node.val - self.prev_val)
24          
25            # Update the previous node value to the current node's value
26            self.prev_val = node.val
27          
28            # Traverse the right subtree
29            in_order_traverse(node.right)
30
31        # Perform the in-order traversal starting from the root
32        in_order_traverse(root)
33
34        # Return the minimum absolute difference found between any two nodes' values
35        return self.min_diff
36

1class Solution {
2    private int minDifference;
3    private int previousValue;
4    private static final int INFINITY = Integer.MAX_VALUE; // Use a static final constant for infinity
5
6    /**
7     * Find the minimum absolute difference between values of any two nodes.
8     *
9     * @param root The root of the binary search tree.
10     * @return The minimum absolute difference.
11     */
12    public int getMinimumDifference(TreeNode root) {
13        minDifference = INFINITY; // Initialize minimum difference to the largest value possible
14        previousValue = INFINITY; // Initialize previous value to the largest value possible for the start
15        inOrderTraversal(root); // Perform in-order traversal to compare node values
16        return minDifference; // Return the smallest difference found
17    }
18
19    /**
20     * Perform in-order traversal on BST to find minimum absolute difference.
21     *
22     * @param node The current node being visited.
23     */
24    private void inOrderTraversal(TreeNode node) {
25        if (node == null) {
26            return; // Base case: if node is null, return to stop the traversal
27        }
28        inOrderTraversal(node.left); // Visit left subtree
29      
30        // Compute the minimum difference with the previous value (if not first node)
31        if (previousValue != INFINITY) {
32            minDifference = Math.min(minDifference, Math.abs(node.val - previousValue));
33        }
34        previousValue = node.val; // Update the previous value to the current node's value
35
36        inOrderTraversal(node.right); // Visit right subtree
37    }
38}
39
40/**
41 * Definition for a binary tree node.
42 */
43class TreeNode {
44    int val;
45    TreeNode left;
46    TreeNode right;
47
48    TreeNode() {}
49
50    TreeNode(int val) {
51        this.val = val;
52    }
53
54    TreeNode(int val, TreeNode left, TreeNode right) {
55        this.val = val;
56        this.left = left;
57        this.right = right;
58    }
59}
60

1#include <climits> // For using INT_MAX
2#include <algorithm> // For using min function
3#include <cstdlib> // For using abs function
4
5// Definition for a binary tree node.
6struct TreeNode {
7    int val;         // Value of the node
8    TreeNode *left;  // Pointer to left child
9    TreeNode *right; // Pointer to right child
10    TreeNode() : val(0), left(nullptr), right(nullptr) {}
11    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
12    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
13};
14
15class Solution {
16public:
17    const int INF = INT_MAX; // Define the maximum possible integer to represent infinity
18    int minDifference;       // To store the minimum absolute difference found
19    int previousValue;       // To store the last node value that was processed in in-order traversal
20
21    // The function to initialize the problem and trigger the depth-first search
22    int getMinimumDifference(TreeNode* root) {
23        minDifference = INF; // Initialize the minimum difference to INF
24        previousValue = INF; // Initialize the previous value as INF to handle the first node's case
25        dfsInorderTraversal(root); // Start the DFS for in-order traversal
26        return minDifference; // Return the final answer (minimum absolute difference)
27    }
28
29    // Recursive function to perform in-order traversal on a binary search tree
30    void dfsInorderTraversal(TreeNode* node) {
31        if (!node) return; // Base case: if the node is null, return
32
33        // Traverse the left subtree
34        dfsInorderTraversal(node->left);
35
36        // Process the current node
37        if (previousValue != INF) { 
38            // If the previous value is valid, update minDifference
39            minDifference = std::min(minDifference, std::abs(previousValue - node->val));
40        }
41        previousValue = node->val; // Update the previous value with the current node's value
42
43        // Traverse the right subtree
44        dfsInorderTraversal(node->right);
45    }
46};
47

1// Import required functions from the standard library.
2import { maxSafeInteger } from "util";
3import { min, abs } from "Math";
4
5// Definition for a binary tree node.
6class TreeNode {
7    val: number;        // Value of the node
8    left: TreeNode | null;   // Pointer to left child
9    right: TreeNode | null;  // Pointer to right child
10    constructor(val: number = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
11        this.val = val;
12        this.left = left;
13        this.right = right;
14    }
15}
16
17// Initialize the maximum possible integer to represent infinity in TypeScript.
18const INF: number = maxSafeInteger;
19// Variables to store the minimum absolute difference and the last node value processed.
20let minDifference: number = INF;
21let previousValue: number = INF;
22
23// Function to initialize the problem and trigger the depth-first search for in-order traversal.
24function getMinimumDifference(root: TreeNode | null): number {
25    minDifference = INF;
26    previousValue = INF;
27    dfsInorderTraversal(root);
28    return minDifference;
29}
30
31// Recursive function to perform in-order traversal on a binary search tree.
32function dfsInorderTraversal(node: TreeNode | null): void {
33    if (!node) return; // If the node is null, exit the function.
34
35    // Traverse the left subtree.
36    dfsInorderTraversal(node.left);
37
38    // Process the current node by updating the minDifference with the absolute difference
39    // between the current node's value and the previous value if previousValue is valid.
40    if (previousValue !== INF) {
41        minDifference = min(minDifference, abs(previousValue - node.val));
42    }
43    // Update the previous value with the current node's value.
44    previousValue = node.val;
45
46    // Traverse the right subtree.
47    dfsInorderTraversal(node.right);
48}
49

Time and Space Complexity

The time complexity of the code is O(n), where n is the number of nodes in the binary tree. This time complexity arises because the depth-first search (DFS) in the function dfs(root) visits each node exactly once. The actions performed on each node—including updating the 'ans' and 'prev' variables—are all O(1) operations, so they do not add to the overall complexity beyond that imposed by the traversal.

The space complexity of the code is O(h), where h is the height of the binary tree. This space complexity is due to the recursive call stack that will grow to the height of the tree in the worst case. For a balanced tree, this would be O(log n), but for a skewed tree (e.g., a tree where each node only has a left or a right child), this could degrade to O(n).

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

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

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don't know