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)