.png)
[Follow here] for daily coding insights
DSA Series Chapter 19 : DELETION IN BINARY TREE(Python Version)
(Using Deepest Rightmost Node)
1. Objective
To delete a given key from a Binary Tree in Python by:
Finding the deepest rightmost node
Replacing the target node’s data
Deleting the deepest node
This approach preserves the complete binary tree structure.
2. Key Concept (Very Important)
In a general Binary Tree:
There is no ordering rule
Deletion cannot use BST logic
Level Order Traversal (BFS) is mandatory
3. Binary Tree Diagram
Before Deletion (Delete 2)
1
/ \
2 3
/ \ /
4 5 6
1
/ \
2 3
/ \ /
4 5 6
After Deletion
1
/ \
6 3
/ \
4 5
1
/ \
6 3
/ \
4 5
4. Deletion Algorithm (Step-by-Step)
If tree is empty → return
Traverse tree using BFS
Identify:
Node containing key (key_node)
Deepest rightmost node (deepest)
Copy deepest node data into key node
Remove deepest node physically
If tree is empty → return
Traverse tree using BFS
Identify:
Node containing key (
key_node)Deepest rightmost node (
deepest)
Copy deepest node data into key node
Remove deepest node physically
5. Node Class 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
6. Function to Delete Deepest Node
from collections import deque
def delete_deepest(root, d_node):
q = deque([root])
while q:
temp = q.popleft()
if temp.left:
if temp.left == d_node:
temp.left = None
return
q.append(temp.left)
if temp.right:
if temp.right == d_node:
temp.right = None
return
q.append(temp.right)
from collections import deque
def delete_deepest(root, d_node):
q = deque([root])
while q:
temp = q.popleft()
if temp.left:
if temp.left == d_node:
temp.left = None
return
q.append(temp.left)
if temp.right:
if temp.right == d_node:
temp.right = None
return
q.append(temp.right)
Explanation
BFS traversal
Parent of deepest node is found
Reference is removed (Python GC handles memory)
BFS traversal
Parent of deepest node is found
Reference is removed (Python GC handles memory)
7. Main Deletion Function
def delete_node(root, key):
if root is None:
return None
if root.left is None and root.right is None:
if root.data == key:
return None
else:
return root
q = deque([root])
key_node = None
temp = None
while q:
temp = q.popleft()
if temp.data == key:
key_node = temp
if temp.left:
q.append(temp.left)
if temp.right:
q.append(temp.right)
if key_node:
key_node.data = temp.data
delete_deepest(root, temp)
return root
def delete_node(root, key):
if root is None:
return None
if root.left is None and root.right is None:
if root.data == key:
return None
else:
return root
q = deque([root])
key_node = None
temp = None
while q:
temp = q.popleft()
if temp.data == key:
key_node = temp
if temp.left:
q.append(temp.left)
if temp.right:
q.append(temp.right)
if key_node:
key_node.data = temp.data
delete_deepest(root, temp)
return root
8. Inorder Traversal (Verification)
def inorder(root):
if root:
inorder(root.left)
print(root.data, end=" ")
inorder(root.right)
def inorder(root):
if root:
inorder(root.left)
print(root.data, end=" ")
inorder(root.right)
9. Complete Python Program
from collections import deque
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def delete_deepest(root, d_node):
q = deque([root])
while q:
temp = q.popleft()
if temp.left:
if temp.left == d_node:
temp.left = None
return
q.append(temp.left)
if temp.right:
if temp.right == d_node:
temp.right = None
return
q.append(temp.right)
def delete_node(root, key):
if root is None:
return None
if root.left is None and root.right is None:
return None if root.data == key else root
q = deque([root])
key_node = None
temp = None
while q:
temp = q.popleft()
if temp.data == key:
key_node = temp
if temp.left:
q.append(temp.left)
if temp.right:
q.append(temp.right)
if key_node:
key_node.data = temp.data
delete_deepest(root, temp)
return root
def inorder(root):
if root:
inorder(root.left)
print(root.data, end=" ")
inorder(root.right)
# Driver Code
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)
print("Before Deletion (Inorder):")
inorder(root)
root = delete_node(root, 2)
print("\nAfter Deletion (Inorder):")
inorder(root)
from collections import deque
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def delete_deepest(root, d_node):
q = deque([root])
while q:
temp = q.popleft()
if temp.left:
if temp.left == d_node:
temp.left = None
return
q.append(temp.left)
if temp.right:
if temp.right == d_node:
temp.right = None
return
q.append(temp.right)
def delete_node(root, key):
if root is None:
return None
if root.left is None and root.right is None:
return None if root.data == key else root
q = deque([root])
key_node = None
temp = None
while q:
temp = q.popleft()
if temp.data == key:
key_node = temp
if temp.left:
q.append(temp.left)
if temp.right:
q.append(temp.right)
if key_node:
key_node.data = temp.data
delete_deepest(root, temp)
return root
def inorder(root):
if root:
inorder(root.left)
print(root.data, end=" ")
inorder(root.right)
# Driver Code
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)
print("Before Deletion (Inorder):")
inorder(root)
root = delete_node(root, 2)
print("\nAfter Deletion (Inorder):")
inorder(root)
10. Output
Before Deletion (Inorder):
4 2 5 1 6 3
After Deletion (Inorder):
4 6 5 1 3
Before Deletion (Inorder):
4 2 5 1 6 3
After Deletion (Inorder):
4 6 5 1 3
11. Time and Space Complexity
| Operation | Complexity |
|---|---|
| Deletion | O(n) |
| Space | O(n) |
12. C vs Python Deletion Comparison
| Aspect | C | Python |
|---|---|---|
| Memory Free | free() | Garbage Collection |
| Queue | Manual | deque |
| Root Update | Pointer | Return root |
| Complexity | O(n) | O(n) |
13. Common Student Mistakes
Applying BST deletion logic
Forgetting to delete deepest node
Ignoring BFS requirement
Not handling single-node tree
Applying BST deletion logic
Forgetting to delete deepest node
Ignoring BFS requirement
Not handling single-node tree
14. Learning Outcome
After this post, students can:
Delete nodes correctly in Binary Tree
Apply BFS for deletion
Translate C deletion logic into Python
Maintain complete binary tree structure
ALSO CHECK
ALSO CHECK
Comments
Post a Comment