# Binary Tree To DLL

Last updated: 29th Aug, 2020

#### Problem Statment

Given a Binary Tree (BT), convert it to a Doubly Linked List(DLL) In-Place. The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (leftmost node in BT) must be the head node of the DLL.

Example 1:
Input:
1
/ \
3 2
Output:
3 1 2
2 1 3
Method:

- Check if the right node is there if yes then assign function to convert the right node into DLL to the head.
- If its head the left node is root.
- And right node is head.
- If the root has left node then assign function to convert the left node into DLL to the head.
- Otherwise,head is the root.
- The function returns the head.

###### Python Code

    def bToDLL(root,head=None):

        if root.right:
            head = bToDLL(root.right, head)
        if head:
            head.left = root
            root.right = head
        if root.left:
            head = bToDLL(root.left, root)
        else:
            head = root
        return head

    from collections import deque
    class Node:
        """ Class Node """
        def __init__(self, value):
            self.left = None
            self.data = value
            self.right = None

    # Function to Build Tree
    def buildTree(s):
        #Corner Case
        if(len(s)==0 or s[0]=="N"):
            return None

        # Creating list of strings from input
        # string after spliting by space
        ip=list(map(str,s.split()))

        # Create the root of the tree
        root=Node(int(ip[0]))
        size=0
        q=deque()

        # Push the root to the queue
        q.append(root)
        size=size+1

        # Starting from the second element
        i=1
        while(size>0 and i=len(ip)):
                break
            currVal=ip[i]

            # If the right child is not null
            if(currVal!="N"):

                # Create the right child for the current node
                currNode.right=Node(int(currVal))

                # Push it to the queue
                q.append(currNode.right)
                size=size+1
            i=i+1
        return root

    import sys
    def printDLL(head): #Print util function to print Linked List
        prev = None
        sys.stdout.flush()
        while(head != None):
            print(head.data, end=" ")
            prev=head
            head=head.right
        print('')
        while(prev != None):
            print(prev.data, end=" ")
            prev=prev.left
        print('')

    if __name__=='__main__':
        t=int(input())
        for _ in range(0,t):
            s=input()
            root=buildTree(s)
            head = bToDLL(root)
            printDLL(head)