🗑️ Deletion in Binary Tree

Follow Me

Binary Tree deletion can be done in various ways depending on the type of tree.

✅ 1. Deletion in a Binary Tree

We delete the node by replacing it with the deepest rightmost node, and then delete that deepest node.

🔧 Steps:

1. Find the node to be deleted.

2. Find the deepest rightmost node.

3. Replace the target node's data with that node's data.

4. Delete the deepest node.

🧠 Python Code (General Binary Tree)

from collections import deque class Node: def __init__(self, data): self.data = data self.left = None self.right = None # Helper to find the deepest node def get_deepest_node(root): q = deque([root]) while q: node = q.popleft() if node.left: q.append(node.left) if node.right: q.append(node.right) return node # Helper to delete the deepest node def delete_deepest(root, d_node): q = deque([root]) while q: node = q.popleft() if node is d_node: node = None return if node.left: if node.left is d_node: node.left = None return else: q.append(node.left) if node.right: if node.right is d_node: node.right = None return else: q.append(node.right) # Main delete 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 key_node = None q = deque([root]) while q: node = q.popleft() if node.data == key: key_node = node if node.left: q.append(node.left) if node.right: q.append(node.right) if key_node: deepest_node = get_deepest_node(root) key_node.data = deepest_node.data delete_deepest(root, deepest_node) return root

🔁 Example Usage:

# Build Tree root = Node(10) root.left = Node(11) root.left.left = Node(7) root.right = Node(9) root.right.left = Node(15) root.right.right = Node(8) # Delete node print("Before deletion (Level Order):") level_order_print(root) root = delete_node(root, 11) print("\nAfter deletion of 11 (Level Order):") level_order_print(root)

🖨️ Level Order Print Helper

def level_order_print(root): if not root: return q = deque([root]) while q: node = q.popleft() print(node.data, end=' ') if node.left: q.append(node.left) if node.right: q.append(node.right)