530. Minimum Absolute Difference in BST

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

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.

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.

  1. During the traversal, we keep track of the value of the previously processed node.
  2. At each current node, we calculate the absolute difference between the current node's value and the previously visited node's value.
  3. We keep an ongoing count of the minimum absolute difference encountered so far.
  4. 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.

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

How does merge sort divide the problem into subproblems?

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:

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. Once the current node has been processed, the dfs function recursively calls itself on the right child to complete the in-order visitation pattern.

  7. 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.

  8. 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.

  9. 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:

1    def in_order_traversal(node):
2        if node is not None:
3            in_order_traversal(node.left)
4            process(node)
5            in_order_traversal(node.right)
6  
7    def process(node):
8        update_minimum_difference(previous_node_value, node.value)
9        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.

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

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Example Walkthrough

Consider the following BST for this example:

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

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.

  1. 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.

  2. Process node 1: This is the first node, so there's no previous node to compare with. Set prev to 1.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. 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
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which of these pictures shows the visit order of a depth-first search?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used in a depth first search?

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 ๐Ÿ‘จโ€๐Ÿซ