# Python solution with detailed explanation

• Solution

Recover Binary Search Tree https://leetcode.com/problems/recover-binary-search-tree/?tab=Description

Algorithm

1. Use a tree example: [100, 50, 200, 25, 75, 99, 400]
2. Sorted Order: 25,50,75,100,150,200,400
3. You can have out of order 50 and 200: 25,200,75,100,150,50,400. Notice in this case we have 2 out of order pairs: (200,75) and (150,50). Simply swap 200 and 50.
4. What if 25/50 or 200/400 are swapped? In that case we will have just one out of order element.
5. 3 and 4 give us our algorithm.
``````class Solution(object):
def recoverTree(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
self.order = []
self.prev = None
self.inorder(root)
if len(self.order) == 2:
self.swap(self.order[0][0], self.order[1][1])
elif len(self.order) == 1:
self.swap(self.order[0][0], self.order[0][1])
return

def inorder(self, root):
if root == None:
return
self.inorder(root.left)
if self.prev and self.prev.val > root.val:
self.order.append((self.prev, root))
self.prev = root
self.inorder(root.right)
return

def swap(self, r1, r2):
r1.val, r2.val = r2.val, r1.val
return
``````

• i come up with the same idea and like your explanation. and here is my implementation.

``````class Solution(object):
def recoverTree(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""

first, second = None, None

stack, node, prev = [], root, None
while stack or node:
if node:
stack.append(node)
node = node.left
else:
node = stack.pop()
if prev and prev.val > node.val:
if not first and not second:
first, second = prev, node
else:
second = node

prev, node = node, node.right

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

``````

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