In a Binary Tree, insertion is generally done level-wise (BFS) — meaning we insert a new node at the first available position from top to bottom and left to right.
✅ Steps for Insertion
-
If the tree is empty, the new node becomes the root.
-
Otherwise, do level-order traversal using a queue.
-
Insert the new node where a left or right child is missing.
🧠 Python Code for Insertion
class Node:
def __init__(self, key):
self.data = key
self.left = None
self.right = None
def insert(root, key):
if not root:
return Node(key)
queue = [root]
while queue:
temp = queue.pop(0)
if not temp.left:
temp.left = Node(key)
return root
else:
queue.append(temp.left)
if not temp.right:
temp.right = Node(key)
return root
else:
queue.append(temp.right)
# Helper to print level order (for checking)
def level_order(root):
if not root:
return
queue = [root]
while queue:
temp = queue.pop(0)
print(temp.data, end=" ")
if temp.left:
queue.append(temp.left)
if temp.right:
queue.append(temp.right)
# Example
root = Node(10)
root = insert(root, 20)
root = insert(root, 30)
root = insert(root, 40)
print("Level Order Traversal:")
level_order(root)
⚡ Example Output:
Level Order Traversal:
10 20 30 40
🟢 Advantages:
-
Simple insertion using BFS.
-
Maintains balance (in terms of completeness) if inserting into a Complete Binary Tree.
🔴 Disadvantages:
-
Not suitable for ordered data (for that, use Binary Search Tree (BST) instead).
No comments:
Post a Comment