Minimum Difference Between BST Nodes

Given a Binary Search Tree (BST) with the root node root, return the minimum difference between the values of any two different nodes in the tree.

Question

Given a Binary Search Tree (BST) with the root node root, return the minimum difference between the values of any two different nodes in the tree.

Example:

Input: root = {4,2,6,1,3,#,#}
Output: 1
Explanation:
Note that root is a TreeNode object, not an array.

The given tree {4,2,6,1,3,#,#} is represented by the following diagram:

          4
        /   \
      2      6
     / \    
    1   3  

while the minimum difference in this tree is 1, it occurs between node 1 and node 2, also between node 3 and node 2.


Input: root = {5,1,8}
Output: 3
Explanation:
Note that root is a TreeNode object, not an array.

The given tree {5,1,8} is represented by the following diagram:

     5
   /   \
 1      8
 
while the minimum difference in this tree is 3, it occurs between node 5 and node 8.

Analyzation

Queue

Simply create a queue and compare each pair from the first element of the queue.

The Code

class Solution:
    """
    @param root: the root
    @return: the minimum difference between the values of any two different nodes in the tree
    """
    def minDiffInBST(self, root):
        # Write your code here
        nodes = []
        queue = [root]
        
        while queue:
            point = queue.pop(0)
            nodes.append(point.val)
            
            if point.left:
                queue.append(point.left)
            if point.right:
                queue.append(point.right)
        
        nodes.sort()
        result = sys.maxsize
        # start from the second index and compare with the previous value
        for index, value in enumerate(nodes[1::]):
            result = min(result, value - nodes[index])
        
        return result

Time & Space Complexity

• Time complexity: O(n). Remember that the best case of a Binary Tree is O(logn) since it is a balanced tree but the worst case is O(n) because it can skew to only one side.
• Space complexity: O(n). Remember that the space complexity is always about how many nodes there are in a Binary Tree. If the tree is well-balanced then it is O(logn) but the worst case will be O(n).