Trees
Master hierarchical data structures step by step
🌳 What are Trees?
Trees are hierarchical data structures that consist of nodes connected by edges. Think of them like a family tree or an organizational chart - there's a clear hierarchy with a root at the top and branches extending downward.
# Simple tree node structure
class TreeNode:
def __init__(self, data):
self.data = data
self.children = []
def add_child(self, child):
self.children.append(child)
# Create a simple tree
root = TreeNode("CEO")
root.add_child(TreeNode("CTO"))
root.add_child(TreeNode("CFO"))
O(log n)
Search Time
Hierarchical
Structure
Recursive
Nature
Tree Characteristics
Hierarchical
Parent-child relationships
Root node
Leaf nodes
Recursive
Each subtree is also a tree
Divide & conquer
Natural recursion
Acyclic
No cycles or loops
Connected
No redundancy
Efficient
Fast search and operations
Logarithmic time
Balanced trees
Lesson 1: Understanding Tree Terminology
Let's learn the essential terms used when working with trees:
Tree Structure Example
A (Root)
/ \
B C
/ / \
D E F (Leaves)
Tree Terminology
class TreeNode:
def __init__(self, data):
self.data = data
self.children = []
self.parent = None
def add_child(self, child):
child.parent = self
self.children.append(child)
def get_level(self):
"""Get the level/depth of this node"""
level = 0
p = self.parent
while p:
level += 1
p = p.parent
return level
def print_tree(self):
"""Print the tree structure"""
spaces = ' ' * self.get_level() * 3
prefix = spaces + "|__" if self.parent else ""
print(prefix + self.data)
if self.children:
for child in self.children:
child.print_tree()
# Build the example tree
root = TreeNode("A") # Root node
b = TreeNode("B") # Internal node
c = TreeNode("C") # Internal node
d = TreeNode("D") # Leaf node
e = TreeNode("E") # Leaf node
f = TreeNode("F") # Leaf node
root.add_child(b)
root.add_child(c)
b.add_child(d)
c.add_child(e)
c.add_child(f)
print("Tree Structure:")
root.print_tree()
print(f"\nRoot: {root.data}")
print(f"Leaves: {[node.data for node in [d, e, f]]}")
print(f"Height: {max(d.get_level(), e.get_level(), f.get_level())}")
Lesson 2: Tree Traversal Methods
There are different ways to visit all nodes in a tree:
Tree Traversal Algorithms
🔹Depth-First Search (DFS) - Pre-order
def preorder_traversal(node, result=[]):
"""Visit: Root -> Left -> Right"""
if node:
result.append(node.data) # Visit root first
for child in node.children:
preorder_traversal(child, result)
return result
# Example usage
result = []
preorder_traversal(root, result)
print("Pre-order:", result) # [A, B, D, C, E, F]
🔹Depth-First Search (DFS) - Post-order
def postorder_traversal(node, result=[]):
"""Visit: Left -> Right -> Root"""
if node:
for child in node.children:
postorder_traversal(child, result)
result.append(node.data) # Visit root last
return result
# Example usage
result = []
postorder_traversal(root, result)
print("Post-order:", result) # [D, B, E, F, C, A]
🔹Breadth-First Search (BFS) - Level-order
from collections import deque
def level_order_traversal(root):
"""Visit nodes level by level"""
if not root:
return []
result = []
queue = deque([root])
while queue:
node = queue.popleft()
result.append(node.data)
# Add all children to queue
for child in node.children:
queue.append(child)
return result
# Example usage
result = level_order_traversal(root)
print("Level-order:", result) # [A, B, C, D, E, F]
Lesson 3: Common Tree Operations
Let's implement essential tree operations:
Tree Operations
🔹Search for a node
def search_tree(node, target):
"""Search for a target value in the tree"""
if not node:
return None
if node.data == target:
return node
# Search in all children
for child in node.children:
result = search_tree(child, target)
if result:
return result
return None
# Example usage
found_node = search_tree(root, "E")
if found_node:
print(f"Found node: {found_node.data}")
print(f"Level: {found_node.get_level()}")
🔹Calculate tree height
def tree_height(node):
"""Calculate the height of the tree"""
if not node or not node.children:
return 0
# Find maximum height among all children
max_child_height = 0
for child in node.children:
child_height = tree_height(child)
max_child_height = max(max_child_height, child_height)
return max_child_height + 1
# Example usage
height = tree_height(root)
print(f"Tree height: {height}")
🔹Count total nodes
def count_nodes(node):
"""Count total number of nodes in the tree"""
if not node:
return 0
count = 1 # Count current node
for child in node.children:
count += count_nodes(child)
return count
# Example usage
total_nodes = count_nodes(root)
print(f"Total nodes: {total_nodes}")
🔹Find all leaf nodes
def find_leaves(node, leaves=[]):
"""Find all leaf nodes in the tree"""
if not node:
return leaves
# If no children, it's a leaf
if not node.children:
leaves.append(node.data)
else:
# Recursively check children
for child in node.children:
find_leaves(child, leaves)
return leaves
# Example usage
leaves = []
find_leaves(root, leaves)
print(f"Leaf nodes: {leaves}")
Real-World Applications
File Systems
- Directory structure
- Folder hierarchy
- File organization
- Path navigation
Decision Trees
- Machine learning
- Game AI
- Expert systems
- Classification
Parsing
- Syntax trees
- Expression parsing
- Compiler design
- HTML/XML parsing
Databases
- B-trees
- Index structures
- Query optimization
- Data organization
Practice Project: Family Tree
Let's build a family tree to practice tree operations:
Family Tree Implementation
class FamilyMember:
def __init__(self, name, birth_year=None):
self.name = name
self.birth_year = birth_year
self.children = []
self.parent = None
def add_child(self, child):
child.parent = self
self.children.append(child)
def get_generation(self):
"""Get generation level (0 = oldest ancestor)"""
level = 0
p = self.parent
while p:
level += 1
p = p.parent
return level
def get_siblings(self):
"""Get all siblings"""
if not self.parent:
return []
return [child for child in self.parent.children if child != self]
def get_descendants(self):
"""Get all descendants"""
descendants = []
for child in self.children:
descendants.append(child)
descendants.extend(child.get_descendants())
return descendants
def print_family_tree(self, prefix="", is_last=True):
"""Print the family tree structure"""
connector = "└── " if is_last else "├── "
age_info = f" (born {self.birth_year})" if self.birth_year else ""
print(f"{prefix}{connector}{self.name}{age_info}")
# Prepare prefix for children
extension = " " if is_last else "│ "
new_prefix = prefix + extension
# Print children
for i, child in enumerate(self.children):
is_last_child = (i == len(self.children) - 1)
child.print_family_tree(new_prefix, is_last_child)
# Build a family tree
grandpa = FamilyMember("John Smith", 1940)
dad = FamilyMember("Robert Smith", 1965)
mom = FamilyMember("Mary Smith", 1968)
uncle = FamilyMember("James Smith", 1970)
# Add children to grandpa
grandpa.add_child(dad)
grandpa.add_child(uncle)
# Add grandchildren
alice = FamilyMember("Alice Smith", 1995)
bob = FamilyMember("Bob Smith", 1998)
charlie = FamilyMember("Charlie Smith", 2000)
dad.add_child(alice)
dad.add_child(bob)
uncle.add_child(charlie)
# Display the family tree
print("Smith Family Tree:")
print("=" * 40)
grandpa.print_family_tree()
# Family operations
print(f"\nFamily Statistics:")
print(f"Total family members: {len([grandpa] + grandpa.get_descendants())}")
print(f"Alice's siblings: {[s.name for s in alice.get_siblings()]}")
print(f"Grandpa's descendants: {[d.name for d in grandpa.get_descendants()]}")
print(f"Generation levels: {max(member.get_generation() for member in grandpa.get_descendants()) + 1}")