.png)
DSA Series Chapter 18 – INSERTION IN BINARY TREE (LEVEL ORDER, Python Version)
1. Objective
To implement insertion in a Binary Tree using Level Order Traversal (BFS) in Python, ensuring the tree remains complete after every insertion.
2. Why Level Order Insertion in Binary Tree?
A general Binary Tree:
Does not follow ordering rules (unlike BST)
Must maintain completeness
Inserts nodes left to right, level by level
Therefore, Breadth First Search (BFS) is used.
3. Binary Tree Diagram
Before Inserting 6
1
/ \
2 3
/ \
4 5
After Inserting 6
1
/ \
2 3
/ \ /
4 5 6
4. Core Logic (Algorithm)
If tree is empty → new node becomes root
Use a queue
Traverse nodes level by level
Insert at the first available left or right position
5. Node Class Definition
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
Explanation
data→ value of nodeleft,right→ references to child nodes
6. Level Order Insertion Function
from collections import deque
def insert_level_order(root, data):
new_node = Node(data)
if root is None:
return new_node
q = deque()
q.append(root)
while q:
temp = q.popleft()
if temp.left is None:
temp.left = new_node
return root
else:
q.append(temp.left)
if temp.right is None:
temp.right = new_node
return root
else:
q.append(temp.right)
7. Inorder Traversal (For Verification)
def inorder(root):
if root:
inorder(root.left)
print(root.data, end=" ")
inorder(root.right)
8. Complete Python Program
from collections import deque
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def insert_level_order(root, data):
new_node = Node(data)
if root is None:
return new_node
q = deque()
q.append(root)
while q:
temp = q.popleft()
if temp.left is None:
temp.left = new_node
return root
else:
q.append(temp.left)
if temp.right is None:
temp.right = new_node
return root
else:
q.append(temp.right)
def inorder(root):
if root:
inorder(root.left)
print(root.data, end=" ")
inorder(root.right)
# Driver code
root = None
values = [1, 2, 3, 4, 5, 6]
for val in values:
root = insert_level_order(root, val)
print("Inorder Traversal:")
inorder(root)
9. Output
Inorder Traversal:
4 2 5 1 6 3
10. Time and Space Complexity
Time Complexity
O(n) — worst case traversal to find vacant node
Space Complexity
O(n) — queue storage
11. Comparison: C vs Python (Insertion)
| Aspect | C | Python |
|---|---|---|
| Queue | Manual array | deque |
| Memory | malloc | Automatic |
| Root handling | Double pointer | Return root |
| Readability | Moderate | High |
12. Common Student Mistakes
Using recursion for insertion
Confusing BT insertion with BST insertion
Not returning root when tree is empty
Forgetting to import
deque
13. Exam-Oriented Key Points
Binary Tree insertion uses BFS
Queue is mandatory
Maintains complete binary tree
Time complexity: O(n)
14. Learning Outcome
After this post, students can:
Insert nodes correctly in a Binary Tree
Implement BFS using queue
Translate C logic into Python
Verify tree structure using traversal
ALSO CHECK
ALSO CHECK
Comments
Post a Comment