-
Notifications
You must be signed in to change notification settings - Fork 1
/
Make Binary Tree From Linked List.py
81 lines (68 loc) · 2.24 KB
/
Make Binary Tree From Linked List.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
# Tree Node structure
class Tree:
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Function to make binary tree from linked list.
def convert(head):
# code here
if not head:
return None
# Create the root of the tree
root = Tree(head.data)
queue = [root]
current = head.next
while current:
# Pop the current node from the front of the queue
parent = queue.pop(0)
# Take the next node from the linked list and make it the left child of the current parent node
leftChild = Tree(current.data)
parent.left = leftChild
queue.append(leftChild)
# Move to the next node
current = current.next
if current:
# Take the next node from the linked list and make it the right child of the current parent node
rightChild = Tree(current.data)
parent.right = rightChild
queue.append(rightChild)
# Move to the next node
current = current.next
return root
# Class to convert the linked list to Binary Tree
class Conversion:
# Constructor for storing head of linked list
# and root for the Binary Tree
def __init__(self):
self.head = None
self.root = None
def push(self, new_data):
# Creating a new linked list node and storing data
new_node = ListNode(new_data)
# Make next of new node as head
new_node.next = self.head
# Move the head to point to new node
self.head = new_node
def levelorderTraversal(self, root):
if root is None:
return
# Perform level order traversal using a queue
queue = [root]
result = []
while queue:
node = queue.pop(0)
result.append(node.data)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# Print the level order traversal
print(*result)
# Linked List node
class ListNode:
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.next = None