.png)
[Follow here] for daily coding insights
DSA Series Chapter 28 – Convert Binary Tree to Doubly Linked List (DLL)(Python Version)
1. Node Definition
class Node: def __init__(self, data): self.data = data self.left = None self.right = None
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
2. Conversion Function
def convert_to_dll(root, head_prev): if root is None: return
convert_to_dll(root.left, head_prev)
if head_prev[1] is None: head_prev[0] = root else: root.left = head_prev[1] head_prev[1].right = root
head_prev[1] = root
convert_to_dll(root.right, head_prev)
def convert_to_dll(root, head_prev):
if root is None:
return
convert_to_dll(root.left, head_prev)
if head_prev[1] is None:
head_prev[0] = root
else:
root.left = head_prev[1]
head_prev[1].right = root
head_prev[1] = root
convert_to_dll(root.right, head_prev)
3. Complete Python Program
class Node: def __init__(self, data): self.data = data self.left = None self.right = None
def convert_to_dll(root, head_prev): if root is None: return
convert_to_dll(root.left, head_prev)
if head_prev[1] is None: head_prev[0] = root else: root.left = head_prev[1] head_prev[1].right = root
head_prev[1] = root
convert_to_dll(root.right, head_prev)
def print_dll(head): temp = head while temp: print(temp.data, end=" ") temp = temp.right
# -------- Main --------root = Node(10)root.left = Node(5)root.right = Node(20)root.left.left = Node(3)root.left.right = Node(8)
head_prev = [None, None] # [head, prev]convert_to_dll(root, head_prev)
print("Doubly Linked List:", end=" ")print_dll(head_prev[0])
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def convert_to_dll(root, head_prev):
if root is None:
return
convert_to_dll(root.left, head_prev)
if head_prev[1] is None:
head_prev[0] = root
else:
root.left = head_prev[1]
head_prev[1].right = root
head_prev[1] = root
convert_to_dll(root.right, head_prev)
def print_dll(head):
temp = head
while temp:
print(temp.data, end=" ")
temp = temp.right
# -------- Main --------
root = Node(10)
root.left = Node(5)
root.right = Node(20)
root.left.left = Node(3)
root.left.right = Node(8)
head_prev = [None, None] # [head, prev]
convert_to_dll(root, head_prev)
print("Doubly Linked List:", end=" ")
print_dll(head_prev[0])
4. Output
Doubly Linked List: 3 5 8 10 20
Doubly Linked List: 3 5 8 10 20
16. Key Interview Notes
Uses inorder traversal
In-place conversion
Very popular interview question
Uses inorder traversal
In-place conversion
Very popular interview question
Comments
Post a Comment