# 3 Python solutions: recur/iter inorder, and preorder. O(n)/O(log(n))

• ``````class Solution1(object):
def getMinimumDifference(self, root):
"""
:type root: TreeNode
:rtype: int
Recursive inorder tree walk. Time: O(n) Space: O(log(n))
"""
def inorder(node, pre, res):
"""
"""
if node is None:
return pre, res
pre, res = inorder(node.left, pre, res)
res = min(res, node.val - pre)
pre = node.val
pre, res = inorder(node.right, pre, res)
return pre, res
pre, res = inorder(root, -float('inf'), float('inf'))
return res

class Solution2(object):
def getMinimumDifference(self, root):
"""
:type root: TreeNode
:rtype: int
Iterative inorder tree walk with a stack. Time: O(n) Space: O(log(n))
"""
pre, res = -float('inf'), float('inf')
node = root
stk = []
while node or stk:
while node:
stk.append(node)
node = node.left
node = stk[-1]  # step back from NIL node
res = min(res, stk.pop().val - pre)
pre = node.val
node = node.right
return res

class Solution3(object):
def getMinimumDifference(self, root):
"""
:type root: TreeNode
:rtype: int
Recursive preorder tree walk. Time: O(n) Space: O(log(n))
"""
def preorder(node, pred, succ, res):
"""
At each recursion, ignore node's subtree and compare node with its
current predecessor and current successor.
:param pred: current predecessor of node if ignoring its subtree
:param succ: current successor of node if ignoring its subtree
"""
if node is None:
return res
res = min(res, node.val - pred)
res = min(res, succ - node.val)
res = preorder(node.left, pred, node.val, res)
res = preorder(node.right, node.val, succ, res)
return res
return preorder(root, -float('inf'), float('inf'), float('inf'))
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.