Convert binary tree to doubly linked list

tree_to_dlist.py

class Solution:
    
    def __init__(self):
        self.dummy = DoublyListNode(0)
        self.pre = self.dummy
    
    """
    @param root, the root of tree
    @return: a doubly list node
    """
    def bstToDoublyList(self, root):
        def helper(root):
            if not root:
                return root
            
            helper(root.left)
            node = DoublyListNode(root.val)
            self.pre.next = node
            node.prev  = self.pre
            self.pre = self.pre.next
            
            helper(root.right)
        
        helper(root)
        
        return self.dummy.next

To reuse pinter and save space, we can use the following code:

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

def print_list(head):
    while head:
        print head.val,
        head = head.right

class Solution:
    def __init__(self):
        self.dummy  = Node(-1)
        self.prev = self.dummy

    def helper(self, root):
        if not root:
            return

        self.helper(root.left)
        self.prev.right = root
        root.left = self.prev.right
        self.prev = root
        self.helper(root.right)

    def bt2dlist(self, root):
        if not root:
            return None

        self.helper(root)
        self.dummy.right.left = None
        return self.dummy.right

def main():
    root = Node(10)
    root.left = Node(12)
    root.right = Node(15)
    root.left.left = Node(25);
    root.left.right = Node(30);
    root.right.left = Node(36);

    s = Solution()
    #should print:
    #25 12 30 36 15
    print_list(s.bt2dlist(root))


if __name__ == "__main__":
    main()