class Node:
    ''' class to represent a Node of BST/ linked list'''

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


def printBST(root):
    '''prints the BST in an inorder sequence'''
    if not root:
        return
    else:
        printBST(root.left)
        print
        root.data, " ",
        printBST(root.right)


def printList(head):
    '''prints the linked list in both directions
     to test whether both the 'next' and 'previous' pointers are fine'''
    if not head:
        return
    if head: print
    head.data
    # print forward direction
    h = head
    print
    '[%d]' % (h.data),
    h = h.right
    while h != head:
        print
        '[%d]' % (h.data),
        h = h.right

    print
    ""
    # print in reverse direction
    h = head.left
    print
    '[%d]' % (h.data),
    h = h.left
    while h != head.left:
        print
        '[%d]' % (h.data),
        h = h.left


def BSTToDLL(root):
    ''' main function to take the root of the BST and return the head of the doubly linked list  '''
    prev = None
    head = None
    BSTToDoublyList(root, prev, head)
    return head


def BSTToDoublyList(root, prev, head):
    if (not root): return

    BSTToDoublyList(root.left, prev, head)

    # current node's left points to previous node
    root.left = prev
    if (prev):
        prev.right = root  # Previous node's right points to current node
    else:
        head = root  # If previous is NULL that current node is head

    right = root.right  # Saving right node

    # Now we need to make list created till now as circular
    head.left = root
    root.right = head

    # For right-subtree/parent, current node is in-order predecessor
    prev = root
    BSTToDoublyList(right, prev, head)


if __name__ == "__main__":
    # create the sample BST
    root = a = Node(5)
    b = Node(3)
    c = Node(6)
    d = Node(2)
    e = Node(4)
    f = Node(7)

    a.left, a.right = b, c
    b.left, b.right = d, e
    c.right = f

    printBST(root)

    print("\ncreating to double linked list")
    head = BSTToDLL(root)
    printList(head)