# LeetCode 099Recover Binary Search Tree

## LeetCode 099 Recover Binary Search Tree Problem

``````# 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 recoverTree(self, root):
#     """
#     :type root: TreeNode
#     :rtype: void Do not return anything, modify root in-place instead.
#     """
#     pre = first = second = None
#     while root is not None:
#         if root.left is not None:
#             temp = root.left
#             while temp.right is not None and temp.right != root:
#                 temp = temp.right
#             if temp.right is not None:
#                 if pre is not None and pre.val > root.val:
#                     if first is None:
#                         first = pre
#                     second = root
#                 pre = root
#                 temp.right = None
#                 root = root.right
#             else:
#                 temp.right = root
#                 root = root.left
#         else:
#             if pre is not None and pre.val > root.val:
#                 if first is None:
#                     first = pre
#                 second = root
#             pre = root
#             root = root.right
#     # only two elements are swapped
#     if first is not None and second is not None:
#         first.val, second.val = second.val, first.val

# https://discuss.leetcode.com/topic/3988/no-fancy-algorithm-just-simple-and-powerful-in-order-traversal/2
def __init__(self):
self.first = self.second = None
self.pre = TreeNode(-sys.maxint - 1)

def recoverTree(self, root):
self.traverse(root)
self.first.val, self.second.val = self.second.val, self.first.val

def traverse(self, root):
if root is None:
return
self.traverse(root.left)
if self.pre.val >= root.val:
if self.first is None:
self.first = self.pre
if self.first is not None:
self.second = root
self.pre = root
self.traverse(root.right)

``````

## List of all Recover Binary Search Tree problems

Leetcode 099 Recover Binary Search Tree problem solution in python3 with explanation. This is the best place to expand your knowledge and get prepared for your next interview.

self.val = x

Feedback is the most important part of any website.