Tree data structures are a core concept in computer science, especially in algorithms and system design. In Python, binary trees are commonly used and can be implemented using classes and recursion.
🌳 Binary Tree Basics
Each node contains:
- A value
- A left child
- A right child
🧱 Node Definition
python
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
🔁 Tree Traversals
1. 🌿 In-Order Traversal (Left, Root, Right)
python
def in_order(root):
if root:
in_order(root.left)
print(root.value, end=" ")
in_order(root.right)
2. 🌲 Pre-Order Traversal (Root, Left, Right)
python
def pre_order(root):
if root:
print(root.value, end=" ")
pre_order(root.left)
pre_order(root.right)
3. 🍂 Post-Order Traversal (Left, Right, Root)
python
def post_order(root):
if root:
post_order(root.left)
post_order(root.right)
print(root.value, end=" ")
➕ Insertion in Binary Search Tree (BST)
python
def insert(root, value):
if root is None:
return TreeNode(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
❌ Deletion in Binary Search Tree (BST)
python
def delete(root, value):
if not root:
return root
if value < root.value:
root.left = delete(root.left, value)
elif value > root.value:
root.right = delete(root.right, value)
else:
# Node with only one child or no child
if not root.left:
return root.right
elif not root.right:
return root.left
# Node with two children
min_larger_node = get_min(root.right)
root.value = min_larger_node.value
root.right = delete(root.right, min_larger_node.value)
return root
def get_min(node):
while node.left:
node = node.left
return node
🧪 Sample Usage
python
root = None
values = [50, 30, 20, 40, 70, 60, 80]
for val in values:
root = insert(root, val)
print("In-order: ")
in_order(root)
print("\nDeleting 20...")
root = delete(root, 20)
print("In-order after deletion: ")
in_order(root)
📝 Summary
OperationDescriptionIn-OrderLeft → Root → RightPre-OrderRoot → Left → RightPost-OrderLeft → Right → RootInsertionAdds a value while maintaining BST propertyDeletionHandles all three deletion cases
Understanding tree operations like these is essential for solving problems in recursion, search optimization, and hierarchical data representation.