How to fix or correct a BST by swapping the nodes in Python?

Question

I have an incorrect BST where two nodes are not in the right position. I know that inorder traversal of a BST is sorted. Hence I traverse through the tree with three pointers : first, last, middle. If the current node is less than previous node, I set previous node as first and current node as middle. This is for the first violation. When second violation occurs, I assign last as current node. Now when last is NULL, swap first and middle and when last is not NULL swap first and last. This is what I have done:

class Node:
   def __init__(self,data):
      self.data = data
      self.left = None
      self.right = None


def fixBST(root,first,middle,last,prev):

    if( root ): 


        fixBST( root.left, first, middle, last, prev )

        if (prev and root.data < prev.data): 

            if ( first is None ): 

                first = prev 
                middle = root 

            else:
                last = root


        prev = root


        fixBST( root.right, first, middle, last, prev )
        return (first,middle,last)


def correctBST( root ): 


    first = middle = last = prev = None 


    first,middle,last = fixBST( root, first, middle, last, prev ) 

    if( first and last ): 
              t = first.data 
              first.data = last.data 
              last.data = t 
    elif( first and middle ): 
              t = first.data 
              first.data = middle.data 
              middle.data = t 



def printInorder(node): 

    if (node == None): 
        return
    printInorder(node.left)
    print node.data
    printInorder(node.right) 



root = Node(6)
root.left     = Node(10) 
root.right     = Node(2) 
root.left.left = Node(1) 
#root.left.right = Node(3) 
#root.right.right = Node(12) 
#root.right.left = Node(7) 

print "Inorder Traversal of the original tree \n" 
printInorder(root)

correctBST(root)

print "\nInorder Traversal of the fixed tree \n"
printInorder(root)

I get the same incorrect tree after printing inorder traversal the second time. I believe the first, middle, last values are not getting stored? Am I missing out on something?

EDIT: I edited the code. But still the return value of first, middle and last is None. Is it not the right way?

To clarify: the input is a tree that can be turned into a BST by swapping exactly one pair of values? — Ry-, Mar 08 '19 at 06:09
Yes, two nodes will be out of place and when we swap them, the tree will be a proper BST. — Animeartist, Mar 08 '19 at 06:13

score 0 · Answer 1 · answered Mar 08 '19 at 07:23

You functions fixBST and swap don't do anything. first, middle, and last are confined to the local scope of the fixBST, so yes in this sense they are not stored. Python passes by assignment.

def swap(a,b): 

    t = a 
    a = b 
    b = t 

a, b = 1, 2
swap(a, b)
print(a, b)
# 1 2

What you should do is either return a value and reassign or use global scope:

# Reassign
def swap(a,b): 
    return b, a

a, b = 1, 2
a, b = swap(a, b)
print(a, b)
# 2 1

# Global
a, b = 1, 2
def swap():
    global a
    global b
    t = a
    a = b
    b = t
swap()
print(a, b)
# 2 1

Probably reassign is the way to go.

I edited the code but still the values of first, last and middle are returned as None. — Animeartist, Mar 08 '19 at 07:50

How to fix or correct a BST by swapping the nodes in Python?

1 Answers1