Minimum Distance Between BST Nodes

In a Binary Search Tree (BST), the in-order traversal of the tree will give a sorted sequence of the values. The minimum difference between the values of any two different nodes will be the minimum difference between consecutive values in this sorted sequence.

Let’s break down the solution into simple steps:

  1. In-Order Traversal: Perform an in-order traversal of the BST, which means we visit the left subtree, then the current node, and finally the right subtree.

  2. Calculate Differences: During the traversal, keep track of the previous node’s value. Calculate the difference between the current node’s value and the previous node’s value, and update the minimum difference if the calculated difference is smaller.

  3. Return Minimum Difference: Finally, return the minimum difference found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def minDiffInBST(self, root: Optional[TreeNode]) -> int:
        def in_order(node):
            nonlocal prev, min_diff
            if not node:
                return

            # Visit left subtree
            in_order(node.left)

            # Calculate the difference with previous value
            if prev is not None:
                diff = node.val - prev
                min_diff = min(min_diff, diff)

            # Update previous value
            prev = node.val

            # Visit right subtree
            in_order(node.right)

        prev = None
        min_diff = float('inf')
        in_order(root)
        return min_diff

Example

  • Input: root = [4,2,6,1,3]
  • Sorted sequence: [1, 2, 3, 4, 6]
  • Minimum difference: 1
  • Output: 1

Insights

  • Efficiency: The time complexity of the algorithm is (O(n)), where (n) is the number of nodes in the tree, since we are visiting each node exactly once.
  • Utilizing BST Property: By taking advantage of the sorted order in a BST, we can find the solution in a concise and efficient way.
  • Recursion: The in-order traversal is implemented using recursion, which is a common approach for tree traversal problems.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution(object):
    pre = -float('inf')
    res = float('inf')

    def minDiffInBST(self, root):
        if root.left:
            self.minDiffInBST(root.left)
        self.res = min(self.res, root.val - self.pre)
        self.pre = root.val
        if root.right:
            self.minDiffInBST(root.right)
        return self.res

Case Analysis

What is the traversal strategy?
    Inorder traversal - easy

  1. Any two nodes (grandchild with grand parent is possible)

  2. Identify the base case Minimum num of nodes = 2 (compute the diff and return it)

  3. How do you deal with a leaf node? root.nil?

    • No left child
    • No right child
    • No left or right child
    • Return the minimum
    • Return the 0

  4. What is the unit of work to be done?

    • Start from root and find the difference with left child (store it somewhere)
    • Start from root and find the difference with right child (store it somewhere)
    • BST property must be taken into account

  5. Where should I perform my slice of work? Before - After ? Between?

    • Before the recursive call? min((node.val - node.left.val)abs, (node.val - node.right.val).abs) As long as I have a left child

6, How to keep track of the minimum that we have found so far? - We can have counter array with the smaller value - Initial value can be Infinity - Variable minimum can be Infinity

   You can store it as a parameter
   You can also keep a instance variable inside the class
   
   Gotcha
     - Declaring a local variable inside the recursive method
     - Why?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @return {Integer}

def inorder(root, array)
    if root.nil?
        return
    end
    
    inorder(root.left, array)
    array << root.val
    inorder(root.right, array)    
end

def min_diff_in_bst(root)
    min = Float::INFINITY
    array = []
    
    inorder(root, array)
    
    for i in (0..array.size-2)
       min = [min, array[i+1]-array[i]].min 
    end

    min
end

Problem Classification

The problem falls under ‘Binary Search Trees’ or ‘BSTs’. It involves traversal and comparison of node values in a BST.

‘What’ Components:

  1. Input: The root of a Binary Search Tree (BST).
  2. Output: The minimum difference between the values of any two different nodes in the tree.

This problem is a ‘searching’ and ‘comparison’ problem. It requires the traversal of a BST, comparison of all node pairs, and identification of the minimum difference.

Given a BST, the goal is to find the minimum difference between the values of any two different nodes. This involves traversing all the nodes in the BST, keeping track of the values of the nodes, and identifying the two nodes that have the minimum difference in their values. The traversal and comparison of nodes are common operations in Data Structure-related problems, and the need to find the minimum difference classifies this problem as a ‘searching’ and ‘comparison’ problem within the ‘Data Structures’ domain.

Language Agnostic Coding Drills

  1. Dissecting the code: The code contains the following distinct concepts: a. Class creation and object-oriented programming (OOP) b. Variable initialization (pre and res) c. Recursion (for BST traversal) d. If conditions (to check for left and right children) e. Updating variables within a method f. Accessing object properties g. Returning a value from a method

  2. Ordering the coding concepts/drills: a. Variable initialization: This is the simplest concept. We need to know how to declare variables and assign values to them.

    b. If conditions: Another basic concept that involves checking a condition and executing code based on whether the condition is true or false.

    c. Accessing object properties: This is the process of accessing the properties of an object. This requires an understanding of object-oriented programming concepts.

    d. Class creation and object-oriented programming (OOP): This involves creating a class and defining methods within the class.

    e. Updating variables within a method: This involves understanding how to update variables inside a function or method based on certain conditions.

    f. Recursion: This is a more complex concept that involves a function calling itself. In this code, recursion is used to traverse the BST.

    g. Returning a value from a method: This is the concept of sending a value back from a function or method.

  3. Problem-solving approach: The overall problem-solving approach involves creating a class and defining methods to perform specific tasks. The main task is the “minDiffInBST” method, which uses recursion to traverse the BST and calculate the minimum difference between node values. Here’s the step-by-step process: a. Initialize two variables, “pre” and “res”, to keep track of the previous node value and the minimum difference found so far, respectively. b. Start the recursive traversal from the root of the BST. c. If a left child exists, recursively call the function for the left child. d. Update “res” by calculating the difference between the current node value and the value of “pre”, and keep the minimum of this value and the current “res”. e. Update “pre” to the current node value. f. If a right child exists, recursively call the function for the right child. g. Once the entire BST has been traversed, return “res” which holds the minimum difference between any two nodes in the BST.

Targeted Drills in Python

  1. Coding drills for each concept:

    a. Variable initialization:

    1
2

    x = 5
y = -float('inf')

    b. If conditions:

    1
2
3
4
5

    x = 5
if x > 0:
    print("Positive number")
else:
    print("Non-positive number")

    c. Accessing object properties:

    1
2
3
4
5

    class MyClass:
    def __init__(self):
        self.my_property = 5
my_object = MyClass()
print(my_object.my_property)

    d. Class creation and OOP:

    1
2
3
4
5
6
7

    class MyClass:
    def __init__(self):
        self.my_property = 5
    def display_property(self):
        print(self.my_property)
my_object = MyClass()
my_object.display_property()

    e. Updating variables within a method:

    1
2
3
4
5
6
7
8

    class MyClass:
    def __init__(self):
        self.my_property = 5
    def increment_property(self):
        self.my_property += 1
my_object = MyClass()
my_object.increment_property()
print(my_object.my_property)  # Prints 6

    f. Recursion:

    1
2
3
4
5
6
7

    def countdown(n):
    if n <= 0:
        print("Blastoff!")
    else:
        print(n)
        countdown(n-1)
countdown(5)

    g. Returning a value from a method:

    1
2
3
4

    def add(a, b):
    return a + b
result = add(5, 3)
print(result)  # Prints 8

  2. Problem-specific concepts:

    • Tree traversal is essential for this problem because we have to examine every node in the BST to find the minimum difference. We can perform an in-order traversal (left, root, right) because in a BST, this will process the nodes in ascending order. In Python, we can implement this recursively, as in the original solution. A simple drill could involve printing the values of a BST in order using recursion.

    • Maintaining state across recursive calls is also necessary, as we need to compare the current node’s value with the value of the previous node in the sorted order. This requires maintaining the value of the previous node and the current minimum difference across different recursive calls, which is why they are defined as properties of the Solution class in the original solution. A drill for this concept could involve a recursive function that computes the sum of a list of numbers, which requires maintaining the sum so far as state across recursive calls.

  3. Integration of drills:

    The final solution combines these concepts as follows:

    • We define a class to encapsulate the solution, which allows us to easily maintain state across recursive calls (concept d).

    • We initialize two properties of the class to keep track of the previous node’s value and the minimum difference so far (concept a).

    • We define a recursive function (concept f) to perform an in-order traversal of the BST. In each call of the function:

      • We check if the node has a left child and if so, recursively call the function for the left child (concept b).

      • We compute the difference between the current node’s value and the previous node’s value, update the minimum difference if necessary (concept e), and update the previous node’s value (concept a).

      • We check if the node has a right child and if so, recursively call the function for the right child (concept b).

      • Finally, we return the minimum difference (concept g).