Given a binary search tree with non-negative values, find the minimumabsolute differencebetween values of any two nodes.

Example:

Input:


   1
    \
     3
    /
   2


Output:

1


Explanation:

The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).

Note:There are at least two nodes in this BST.

Iterative Solution using Level Order Traversal(Timeout):

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import Queue
class Solution(object):
    def getMinimumDifference(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return None

        q = Queue.Queue()
        q.put(root)
        node = None
        result = []
        mini = 1234567
        while not q.empty():
            node = q.get()
            result.append(node.val)

            if node.left is not None:
                q.put(node.left)
            if node.right is not None:
                q.put(node.right)

        return min([abs(a-b) for a,b in zip(result, result[1:])])

Recursive Solution using InOrder Traversal(Accepted):

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def getMinimumDifference(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def inorder(node,result=[]):
            if node.left: inorder(node.left,result)
            result.append(node.val)
            if node.right: inorder(node.right,result)
            return result

        result = inorder(root)

        return min([abs(a-b) for a,b in zip(result, result[1:])])