Binary Tree to Double Linked List
In this class, We discuss Binary Tree to Double Linked List.
Readers can prepare a full competitive coding course to crack product development companies. Click Here.
The reader should have basic coding skills to work with competitive coding. Click here.
Question:
Given a binary tree.
Our task is to convert the binary tree into a double-linked list.
The elements in the Double linked list should be in the inorder traversal manner.
Time complexity: O(N)
Space complexity: O(H) H is the height of the binary tree.
The below diagram shows the example.
Logic:
We can implement in-order traversal using recursion and loops.
In this class, we discuss based on loops.
Implement in both ways for better practice.
Logic:
We use stack to implement inorder traversal.
Whenever we display the value in inorder traversal, we use it to maintain a node in the double-linked list.
We use a previous variable to maintain the previous node address.
In a double-linked list, we need to maintain the previous node address.
We provide the step-by-step explanation is provided in the video.
Code:
class Node:
# Constructor to create a new node
def __init__(self, val):
self.data = val
self.left = None
self.right = None
class Solution:
def bToDLL(self,root):
# do Code here
current=root
stack=[]
previous=None
head=None
tmp=None
while(True):
if current is not None:
stack.append(current)
current=current.left
elif(len(stack)>0):
current=stack.pop()
ob=Node(current.data)
if(head==None):
head=ob
previous=ob
else:
previous.right=ob
ob.left=previous
previous=ob
current=current.right
else:
break
return head
if __name__ == ‘__main__’:
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.right.left.right = Node(8)
root.right.right.right = Node(9)
print(“Double Linked List”)
ob=Solution()
z=ob.bToDLL(root)
while(z!=None):
print(z.data)
z=z.right