🧩 Python DSA Patterns — Trees Intro 🌳🐍

A Tree is a hierarchical data structure made up of nodes connected by edges.

The top node is the root, and each node can have child nodes.

Tree traversal means visiting every node in a specific order — either depth-first (DFS) or breadth-first (BFS).

📝 Building a Binary Tree

Let’s define a simple binary tree with a Node class.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# Build a simple binary tree
#         1
#        / \
#       2   3
#      / \
#     4   5

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print("Binary Tree Created:")
print("       1")
print("     /   \\")
print("    2     3")
print("   / \\")
print("  4   5")

📝 Depth-First Traversals (DFS)

DFS explores a branch fully before moving to the next.

There are three main types:

• Preorder (Root → Left → Right)
• Inorder (Left → Root → Right)
• Postorder (Left → Right → Root)

def preorder(node):
    if node:
        print(node.value, end=" ")
        preorder(node.left)
        preorder(node.right)

def inorder(node):
    if node:
        inorder(node.left)
        print(node.value, end=" ")
        inorder(node.right)

def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.value, end=" ")

print("Preorder:", end=" ")
preorder(root)     # 1 2 4 5 3
print("\nInorder:", end=" ")
inorder(root)      # 4 2 5 1 3
print("\nPostorder:", end=" ")
postorder(root)    # 4 5 2 3 1

📝 Breadth-First Traversal (BFS — Level Order)

BFS visits nodes level by level using a queue.

from collections import deque

def level_order(root):
    if not root:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.value, end=" ")
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

print("\nLevel Order:", end=" ")
level_order(root)  # 1 2 3 4 5

✅ Takeaway

• DFS explores deep into one branch before backtracking.
• BFS explores all nodes level by level.
• Both are foundational for more advanced algorithms like Heaps, Tries, and Binary Search Trees.

🏋️ Practice Problems

1. Binary Tree Traversals (Inorder, Preorder, Postorder)
2. Level Order Traversal (BFS)
3. Invert Binary Tree
4. Height of a Binary Tree
5. Check if two trees are identical

📂 Full Script

The blog covers the essentials — find the complete notebook with all snippets & extras on GitHub Repo 👉 Python DSA Patterns