Fixing Two nodes of a BST

'''
Brute force: get the inorder or the tree in an array and then sort the array and traverse the tree again paralleley with the array, replace the element of the node when it is not matching with the ith element of the array.
'''

'''
Logic:
Inorder of BST is always sorted.
If only one node will be swapped in a BST then there is only two possibility:

case1:
eg Inorder: 3 25 7 8 10 15 20 5 swapped nodes(ie. 25, 5) are not adjacent
here the current node ie. 7  is lesser than previous node,ie. 25 so make left=25,middle=7
and again 5 is lesse than 20 so make left=5.
if there is left,middle and right then swap(left,right);

case 2:swapped nodes are adjacent
eg. 3 5 8 7 10 15 20 25
swapped node(ie. 8,7)
using previous case left=8 and middle=7.
no voilation or sorted order again,so no right node so,swap(left,middle)

'''
'''
class Node:
    def __init__(self, val):
        self.right = None
        self.data = val
        self.left = None
'''
def fun(root,dict):
    if root:
        fun(root.left,dict)
        if dict['prev'] and root.data<dict['prev'].data and dict['left']:
            dict['right']=root
        elif dict['prev'] and root.data<dict['prev'].data:
            dict['left']=dict['prev']
            dict['middle']=root
        dict['prev']=root
        fun(root.right,dict)

class Solution:
    def correctBST(self, root):
        dict={'middle':None, 'left':None, 'right':None, 'prev':None}
        fun(root,dict)
        if dict['right']:
            dict['left'].data,dict['right'].data=dict['right'].data,dict['left'].data
        else:
            dict['left'].data,dict['middle'].data=dict['middle'].data,dict['left'].data
        return root