🧠 Mental Model: Family Tree Structure
Think of trees like family genealogies:
- 👑 Root - The oldest ancestor (starting point)
- 👨👩👧👦 Parent-Child - Family relationships (one parent, multiple children)
- 🍃 Leaves - Family members with no descendants
- 📏 Height - Generations from root to furthest descendant
Step 1: Why Do We Need Trees?
Trees solve the fundamental problem of organizing hierarchical data efficiently. They appear everywhere in computer science because they mirror natural organizational structures.
📁 File Systems
Directories and subdirectories form natural tree structures
🔍 Database Indexing
B-trees enable fast data retrieval from massive databases
🌐 Web Pages
HTML DOM elements form hierarchical tree structures
🧮 Expression Parsing
Mathematical expressions represented as parse trees
Step 2: Tree Fundamentals
Trees are hierarchical data structures consisting of nodes connected by edges. Every tree has exactly one path between any two nodes, and there are no cycles.
🎮 Basic Tree Structure
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
# Create a simple tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# 1
# / \
# 2 3
# / \
# 4 5Step 3: Binary Search Trees (BST)
A Binary Search Tree maintains a special property: for every node, all values in the left subtree are smaller, and all values in the right subtree are larger. This enables efficient searching!
🎮 BST Implementation
class BST:
def __init__(self):
self.root = None
def insert(self, value):
if not self.root:
self.root = TreeNode(value)
else:
self._insert_recursive(self.root, value)
def _insert_recursive(self, node, value):
if value < node.value:
if node.left is None:
node.left = TreeNode(value)
else:
self._insert_recursive(node.left, value)
else:
if node.right is None:
node.right = TreeNode(value)
else:
self._insert_recursive(node.right, value)
def search(self, value):
return self._search_recursive(self.root, value)
def _search_recursive(self, node, value):
if not node:
return False
if value == node.value:
return True
elif value < node.value:
return self._search_recursive(node.left, value)
else:
return self._search_recursive(node.right, value)Step 4: Interactive Tree Builder
🎮 Build Your Own BST
Step 5: Tree Traversal Methods
Tree traversal is the process of visiting all nodes in a specific order. Different traversal methods serve different purposes and reveal different aspects of the tree structure.
🚶♂️ In-order Traversal (Left → Root → Right)
def inorder_traversal(node):
result = []
if node:
result.extend(inorder_traversal(node.left)) # Visit left
result.append(node.value) # Visit root
result.extend(inorder_traversal(node.right)) # Visit right
return result
# For BST: gives sorted order! [1, 2, 3, 4, 5]🏃♂️ Pre-order & Post-order Traversals
# Pre-order: Root → Left → Right (good for copying trees)
def preorder_traversal(node):
result = []
if node:
result.append(node.value) # Visit root
result.extend(preorder_traversal(node.left)) # Visit left
result.extend(preorder_traversal(node.right))# Visit right
return result
# Post-order: Left → Right → Root (good for deleting trees)
def postorder_traversal(node):
result = []
if node:
result.extend(postorder_traversal(node.left)) # Visit left
result.extend(postorder_traversal(node.right))# Visit right
result.append(node.value) # Visit root
return result⚠️ Critical Pitfall: The Degenerate Tree Trap
If you insert sorted data into a BST, it becomes a linear chain! This destroys the tree's efficiency.
# ❌ DANGEROUS: Inserting sorted data
bst = BST()
for i in range(1, 8): # 1, 2, 3, 4, 5, 6, 7
bst.insert(i)
# Results in degenerate tree:
# 1
# \
# 2
# \
# 3 (becomes a linked list!)
# Search time: O(n) instead of O(log n)!
# ✅ BETTER: Insert in random order
import random
values = list(range(1, 8))
random.shuffle(values) # [4, 1, 6, 2, 7, 3, 5]
bst = BST()
for value in values:
bst.insert(value)
# Results in balanced tree with O(log n) performance!Step 6: Knowledge Check
Question 1: BST Property
In a Binary Search Tree, what is the key property that must be maintained?
Left children are smaller, right children are larger than parent
All nodes must have exactly two children
The tree must be perfectly balanced
Question 2: Tree Traversal
Which traversal method gives nodes in sorted order for a BST?
Pre-order traversal
In-order traversal
Post-order traversal