# My two Python solutions. Recursive O(logN), iterative O(1) space

• ``````def recover_tree_recursive(self, node):
if not node:
return

def helper(root, prev, l):
if root.left:
prev = helper(root.left, prev, l)
if prev and prev.val > root.val:
if len(l) == 0:
l.append(prev)
l.append(root)
else:
l[1] = root
prev = root
if root.right:
prev = helper(root.right, prev, l)
return prev

p = list()
helper(node, None, p)
if len(p) != 0:
p[0].val, p[1].val = p[1].val, p[0].val

def recover_tree_iterative(self, root):
prev = None
first = None
second = None
while root:
if root.left:
buf = root.left
while buf.right != root and buf.right:
buf = buf.right
if buf.right:
buf.right = root
root = root.left
else:
if prev and prev.val > root.val:
if not first:
first = prev
second = root
prev = root
buf.right = None
root = root.right
else:
if prev and prev.val > root.val:
if not first:
first = prev
second = root
prev = root
root = root.right

if first:
first.val, second.val = second.val, first.val``````

• for the recursive, the space should still be O(n). Think about a tree where each node only has left child, and it will look like a LinkedList

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