Why Trees Matter in Real Life
Trees are everywhere because they naturally represent hierarchical relationships
Anything with a parent-child or belongs-to relationship is a tree!
File Systems
Every folder and file on your computer is organized as a tree! The root is C:\ or /, folders are internal nodes, files are leaves.
HTML/DOM
Every webpage is a tree! The <html> tag is the root, and all other elements are its descendants.
Game AI
Decision trees help game AI choose the best move. Each node represents a game state, edges are possible moves.
Databases
B-trees and B+ trees make database searches lightning fast, even with millions of records!
Auto-complete
When you type in Google, a special tree called a Trie suggests completions instantly!
Organization Charts
Company hierarchies are trees! CEO at the root, managers as internal nodes, employees as leaves.
Understanding Trees - The Basics
Real-World Analogy: Your Family Tree
Think of a tree like your family tree:
Just like how you can trace your family lineage, in a tree data structure, we can trace paths from one node to another!
What Makes a Tree?
A tree is a collection of nodes connected by edges, with these simple rules:
- One special node called the root (top of the tree)
- Every node has exactly one parent (except the root)
- Nodes can have zero or more children
- No cycles (you can't loop back to where you started)
Try It Yourself: Build Your First Tree!
Tree Vocabulary (Made Simple!)
Node
A single element in the tree that stores data
Edge
The connection between two nodes (parent-child link)
Root
The topmost node with no parent (the boss!)
Leaf
A node with no children (end of a branch)
Height
The longest path from root to any leaf
Depth
Distance from root to a specific node
Your First Tree Node in Python
# A tree node is just a box with data and pointers!
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val # The data we store
self.left = left # Pointer to left child
self.right = right # Pointer to right child
# Creating a simple tree:
# 1
# / \
# 2 3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(f"Root value: {root.val}") # Output: 1
print(f"Left child: {root.left.val}") # Output: 2
print(f"Right child: {root.right.val}") # Output: 3Common Beginner Mistake
Forgetting to check if a node exists before accessing it! Always check:
# ✘ Wrong way:
print(root.left.val) # Crashes if left is None!
# ✔ Right way:
if root.left:
print(root.left.val)Tree Traversal Patterns
Think of Tree Traversal Like Exploring a House
Imagine you're exploring a house with multiple rooms and doors:
- Preorder: Note the room, then explore left door, then right door
- Inorder: Explore left door, note the room, then explore right door
- Postorder: Explore both doors first, then note the room
- Level-order: Explore all rooms on floor 1, then floor 2, then floor 3...
1. Inorder Traversal (Left - Root - Right)
Perfect for BSTs - gives you sorted order!
def inorder(root):
if not root:
return []
result = []
# Recursive approach - clean and simple!
def traverse(node):
if node:
traverse(node.left) # Go left
result.append(node.val) # Process node
traverse(node.right) # Go right
traverse(root)
return result
# For tree: 4
# / \
# 2 6
# / \ / \
# 1 3 5 7
# Result: [1, 2, 3, 4, 5, 6, 7] - Sorted!2. Preorder Traversal (Root - Left - Right)
Great for copying trees - process parent before children!
def preorder(root):
if not root:
return []
result = []
def traverse(node):
if node:
result.append(node.val) # Process node first
traverse(node.left) # Then go left
traverse(node.right) # Then go right
traverse(root)
return result
# Same tree, Result: [4, 2, 1, 3, 6, 5, 7]3. Level-Order Traversal (BFS)
Process tree level by level - like reading a book!
from collections import deque
def levelOrder(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(current_level)
return result
# Result: [[4], [2, 6], [1, 3, 5, 7]]Interactive Traversal Visualizer
Practice Problems
Easy Count the Total Number of Nodes
Given a binary tree, return the total number of nodes.
Think recursively: count 1 (current) + all nodes in left subtree + all nodes in right subtree.
def countNodes(root):
"""Count total nodes in the tree"""
if not root:
return 0
# Count: 1 (current) + left subtree + right subtree
return 1 + countNodes(root.left) + countNodes(root.right)
# Even simpler to understand:
def countNodesVerbose(root):
if not root:
return 0
left_count = countNodes(root.left) # Count left side
right_count = countNodes(root.right) # Count right side
return 1 + left_count + right_count # Add them up!Easy Find the Height of a Tree
Return the height (longest path from root to any leaf) of a binary tree.
Height = 1 + max(height of left subtree, height of right subtree). Base case: empty tree has height 0.
def maxDepth(root):
if not root:
return 0
return 1 + max(maxDepth(root.left), maxDepth(root.right))Easy Count Leaf Nodes
Count how many leaf nodes (nodes with no children) exist in the tree.
A leaf node has no left child and no right child.
def countLeaves(root):
if not root:
return 0
if not root.left and not root.right:
return 1
return countLeaves(root.left) + countLeaves(root.right)Medium Invert a Binary Tree
Flip the tree like a mirror image so that every left child becomes a right child and vice versa.
At each node, swap left and right children, then recursively invert both subtrees.
def invertTree(root):
"""Flip the tree like a mirror image"""
if not root:
return None
# Swap left and right children
root.left, root.right = root.right, root.left
# Recursively invert subtrees
invertTree(root.left)
invertTree(root.right)
return root
# Before: 1 After: 1
# / \ / \
# 2 3 3 2Medium Check if Two Trees are Identical
Given two binary trees, determine if they are structurally identical and have the same values.
Two trees are identical if their roots are equal, left subtrees are identical, and right subtrees are identical.
def isSameTree(p, q):
if not p and not q:
return True
if not p or not q:
return False
return (p.val == q.val and
isSameTree(p.left, q.left) and
isSameTree(p.right, q.right))Hard Lowest Common Ancestor (LCA)
Find the lowest common ancestor of two nodes in a binary tree.
If both nodes are found in different subtrees, the current node is the LCA. If both are in the same subtree, recurse into that subtree.
def lowestCommonAncestor(root, p, q):
if not root or root == p or root == q:
return root
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left if left else rightPro Tip
Start with the beginner problems and work your way up. Most tree problems follow similar patterns - once you understand recursion with trees, you can solve 80% of tree problems!
Binary Search Trees (BST)
Like a Dictionary!
A BST is like a dictionary where words before 'M' go to the left, words after 'M' go to the right. This makes finding any word super fast!
BST Property
For every node in a BST:
- All values in the left subtree are smaller
- All values in the right subtree are larger
- This property holds for every single node
Complete BST Implementation
class BST:
def __init__(self):
self.root = None
def insert(self, val):
"""Insert a value into the BST"""
if not self.root:
self.root = TreeNode(val)
return
current = self.root
while True:
if val < current.val:
if not current.left:
current.left = TreeNode(val)
break
current = current.left
else:
if not current.right:
current.right = TreeNode(val)
break
current = current.right
def search(self, val):
"""Search for a value - O(log n) average!"""
current = self.root
while current:
if val == current.val:
return True
elif val < current.val:
current = current.left
else:
current = current.right
return False
# Using the BST
bst = BST()
for val in [5, 3, 7, 1, 9]:
bst.insert(val)
print(bst.search(7)) # True - found it!
print(bst.search(6)) # False - not thereValidating a BST
def isValidBST(root):
"""Check if a tree is a valid BST"""
def validate(node, min_val, max_val):
if not node:
return True
# Check if current node violates BST property
if node.val <= min_val or node.val >= max_val:
return False
# Recursively validate subtrees with updated bounds
return (validate(node.left, min_val, node.val) and
validate(node.right, node.val, max_val))
return validate(root, float('-inf'), float('inf'))Common BST Mistake
Checking only immediate children isn't enough! You must ensure ALL nodes in left subtree are smaller, not just the immediate left child.
Quick Reference Guide
Time Complexity Cheat Sheet
| Operation | Average Case | Worst Case | When to Use |
|---|---|---|---|
| BST Search | O(log n) | O(n) | When data is sortable |
| BST Insert | O(log n) | O(n) | Maintaining sorted data |
| Tree Traversal | O(n) | O(n) | Processing all nodes |
| Find Height | O(n) | O(n) | Tree metrics |
| Level Order | O(n) | O(n) | Level-wise processing |
When to Use Each Traversal
| Traversal | Order | Best For |
|---|---|---|
| Inorder | Left - Root - Right | Getting sorted values from BST |
| Preorder | Root - Left - Right | Copying/serializing trees |
| Postorder | Left - Right - Root | Deleting trees, calculating sizes |
| Level-order | Level by level | Finding minimum depth, printing levels |
Essential Tree Patterns
Recursion Pattern
def treePattern(root):
if not root: # Base case
return something
# Process current
# Recurse left
# Recurse right
return resultLevel-order Pattern
queue = deque([root])
while queue:
size = len(queue)
for _ in range(size):
node = queue.popleft()
# Process node
# Add childrenRemember
Trees are recursive structures - most tree problems have elegant recursive solutions. Think: "What should I do at this node?" and "What should my children do?"