Think of a family tree or an organization chart. A tree is a data structure that looks like an upside-down tree, where:
- The root is at the top (like a CEO)
- Branches connect different levels
- Leaves are at the bottom (employees with no subordinates)
- Each item is called a node
Real-world analogy: A company hierarchy where each manager can have multiple employees, but each employee has only one direct boss.
Tree Terminology: #
- Root: The top node (CEO)
- Parent: A node that has children (Manager)
- Child: A node that has a parent (Employee)
- Leaf: A node with no children (Entry-level employee)
- Height: Levels from root to deepest leaf
- Depth: Levels from root to a specific node
1. Binary Trees #
What is it? #
A binary tree is like a family tree where each person can have at most 2 children (left child and right child).
Structure: #
A
/ \
B C
/ \ \
D E F
Real-world Example: Decision Tree #
Think of a “20 Questions” game:
- Each question has only 2 answers: Yes or No
- Based on your answer, you go left (No) or right (Yes)
- You continue until you reach the final answer
Example Decision Tree: “Guess the Animal”
Is it a mammal?
/ \
No/ \Yes
/ \
Is it a bird? Does it live on land?
/ \ / \
No/ \Yes No/ \Yes
Fish Bird Whale Dog
Simple Code Example (Python): #
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class BinaryTree:
def __init__(self, root_data):
self.root = TreeNode(root_data)
def add_left_child(self, parent_node, data):
parent_node.left = TreeNode(data)
return parent_node.left
def add_right_child(self, parent_node, data):
parent_node.right = TreeNode(data)
return parent_node.right
def print_tree(self, node, level=0):
if node:
self.print_tree(node.right, level + 1)
print(" " * level + str(node.data))
self.print_tree(node.left, level + 1)
# Usage - Creating the animal guessing tree
tree = BinaryTree("Is it a mammal?")
root = tree.root
# Left side (No - not a mammal)
bird_question = tree.add_left_child(root, "Is it a bird?")
tree.add_left_child(bird_question, "Fish")
tree.add_right_child(bird_question, "Bird")
# Right side (Yes - is a mammal)
land_question = tree.add_right_child(root, "Does it live on land?")
tree.add_left_child(land_question, "Whale")
tree.add_right_child(land_question, "Dog")
tree.print_tree(tree.root)
Use Cases: #
- Decision trees in AI
- File system directories
- HTML/XML document structure
- Mathematical expression trees
2. Binary Search Trees (BST) #
What is it? #
A Binary Search Tree is like a sorted binary tree with a special rule:
- Left child is always smaller than parent
- Right child is always larger than parent
- This makes searching super fast (like a phone book)
Structure: #
50
/ \
30 70
/ \ / \
20 40 60 80
Real-world Example: Company Employee ID System #
Imagine organizing employee IDs for quick lookup:
- Boss has ID 50
- Employees with smaller IDs (30, 20, 40) go to the left
- Employees with larger IDs (70, 60, 80) go to the right
Simple Code Example (Python): #
class BSTNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, data):
if not self.root:
self.root = BSTNode(data)
else:
self._insert_recursive(self.root, data)
def _insert_recursive(self, node, data):
if data < node.data:
if node.left is None:
node.left = BSTNode(data)
else:
self._insert_recursive(node.left, data)
else:
if node.right is None:
node.right = BSTNode(data)
else:
self._insert_recursive(node.right, data)
def search(self, data):
return self._search_recursive(self.root, data)
def _search_recursive(self, node, data):
if not node:
return False
if data == node.data:
return True
elif data < node.data:
return self._search_recursive(node.left, data)
else:
return self._search_recursive(node.right, data)
def print_sorted(self, node):
# In-order traversal gives sorted output
if node:
self.print_sorted(node.left)
print(node.data, end=" ")
self.print_sorted(node.right)
# Usage - Employee ID system
company_bst = BinarySearchTree()
# Adding employee IDs
employee_ids = [50, 30, 70, 20, 40, 60, 80]
for emp_id in employee_ids:
company_bst.insert(emp_id)
print("Employee IDs in sorted order:")
company_bst.print_sorted(company_bst.root) # Output: 20 30 40 50 60 70 80
print(f"\nIs employee 40 in system? {company_bst.search(40)}") # True
print(f"Is employee 90 in system? {company_bst.search(90)}") # False
Advantages of BST: #
- Fast searching: O(log n) average time
- Automatic sorting: In-order traversal gives sorted data
- Efficient insertion/deletion
Disadvantages: #
- Can become unbalanced (like a linked list)
- Worst case: O(n) time complexity
3. Tree Traversals #
Tree traversal is like visiting every room in a house. There are different ways to do it:
1. In-Order Traversal (Left → Root → Right) #
Like reading a book: Left page, then middle, then right page
Process: Left subtree → Current node → Right subtree
Real-world analogy: Organizing books on a shelf from left to right
2. Pre-Order Traversal (Root → Left → Right) #
Like making a backup: Save the folder first, then its contents
Process: Current node → Left subtree → Right subtree
Real-world analogy: Company announcement flows from CEO down to employees
3. Post-Order Traversal (Left → Right → Root) #
Like calculating folder sizes: Calculate subfolder sizes first, then main folder
Process: Left subtree → Right subtree → Current node
Real-world analogy: Calculating total expenses (departments first, then company total)
Code Example for All Traversals: #
class TreeTraversal:
def __init__(self, root):
self.root = root
def inorder(self, node, result=[]):
"""Left → Root → Right (gives sorted output for BST)"""
if node:
self.inorder(node.left, result)
result.append(node.data)
self.inorder(node.right, result)
return result
def preorder(self, node, result=[]):
"""Root → Left → Right (good for copying tree)"""
if node:
result.append(node.data)
self.preorder(node.left, result)
self.preorder(node.right, result)
return result
def postorder(self, node, result=[]):
"""Left → Right → Root (good for deleting tree)"""
if node:
self.postorder(node.left, result)
self.postorder(node.right, result)
result.append(node.data)
return result
# Example with our BST
traversal = TreeTraversal(company_bst.root)
print("In-order (sorted):", traversal.inorder(company_bst.root, []))
# Output: [20, 30, 40, 50, 60, 70, 80]
print("Pre-order (root first):", traversal.preorder(company_bst.root, []))
# Output: [50, 30, 20, 40, 70, 60, 80]
print("Post-order (root last):", traversal.postorder(company_bst.root, []))
# Output: [20, 40, 30, 60, 80, 70, 50]
When to Use Each Traversal: #
In-Order:
- Getting sorted data from BST
- Mathematical expression evaluation
Pre-Order:
- Copying/cloning a tree
- Prefix expression evaluation
- File system backup
Post-Order:
- Deleting a tree safely
- Calculating directory sizes
- Postfix expression evaluation
4. Balanced Trees Overview #
The Problem with Regular BST #
Imagine adding numbers in order: 1, 2, 3, 4, 5
1
\
2
\
3
\
4
\
5
This becomes like a linked list – very slow!
What are Balanced Trees? #
Balanced trees automatically reorganize themselves to stay “balanced” (short and wide, not tall and skinny).
AVL Trees #
What is it?: Named after its inventors (Adelson-Velsky and Landis)
- Self-balancing BST
- Height difference between left and right subtrees is at most 1
- Automatic rotations keep it balanced
Real-world analogy: Like a mobile (hanging decoration) that stays balanced
# Simplified AVL concept (not full implementation)
class AVLNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
self.height = 1 # Height of this node
def get_height(node):
if not node:
return 0
return node.height
def get_balance(node):
if not node:
return 0
return get_height(node.left) - get_height(node.right)
# If balance factor is > 1 or < -1, we need to rotate
def is_balanced(node):
balance = get_balance(node)
return -1 <= balance <= 1
When to use AVL:
- When you need guaranteed fast searches
- Database indexing
- When insertions/deletions are less frequent than searches
Red-Black Trees #
What is it?: Another self-balancing BST with these rules:
- Every node is either red or black
- Root is always black
- Red nodes can’t have red children
- All paths from root to leaves have same number of black nodes
Real-world analogy: Like traffic lights with rules to prevent traffic jams
# Simplified Red-Black concept
class RBNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
self.color = "RED" # New nodes are red
self.parent = None
# Red-Black rules ensure the tree stays balanced
# Complex rotations and recoloring maintain these rules
When to use Red-Black:
- When you need good performance for all operations
- Java’s TreeMap and TreeSet
- Linux kernel’s scheduler
- More insertions/deletions than AVL can handle efficiently
Comparison: #
Feature | Regular BST | AVL Tree | Red-Black Tree |
---|---|---|---|
Search Time | O(n) worst | O(log n) | O(log n) |
Insert Time | O(n) worst | O(log n) | O(log n) |
Balance | No | Strict | Loose |
Rotations | None | More | Fewer |
Memory | Less | More | More |
Real-World Applications #
1. File Systems #
C:\
├── Users\
│ ├── Alice\
│ └── Bob\
├── Program Files\
│ ├── Microsoft\
│ └── Adobe\
└── Windows\
Type: General tree (not binary)
2. Database Indexing #
- B-trees and B+ trees (variations of balanced trees)
- Used in MySQL, PostgreSQL, MongoDB
- Enable fast data retrieval
3. Decision Making Systems #
- Decision trees in machine learning
- Medical diagnosis systems
- Loan approval systems
4. Game Development #
- Game trees for AI (chess, checkers)
- Scene graphs for 3D graphics
- Collision detection systems
5. Compilers #
- Abstract Syntax Trees (AST)
- Parse trees for code analysis
- Expression evaluation
6. Network Routing #
- Spanning trees in network protocols
- Shortest path algorithms
- Network topology management
7. Autocomplete/Search #
- Trie trees for word suggestions
- Search engines
- Spell checkers
When to Use Which Tree #
Use Binary Tree When: #
- Simple hierarchical data
- Decision-making processes
- Expression parsing
Use BST When: #
- Need sorted data
- Frequent searching
- Data doesn’t come in sorted order
Use AVL Tree When: #
- Need guaranteed fast searches
- More searches than insertions
- Database applications
Use Red-Black Tree When: #
- Balanced performance for all operations
- Frequent insertions and deletions
- General-purpose applications
Summary #
Trees are like organizational charts in the digital world:
- Binary Trees: Each node has at most 2 children (like a simple family tree)
- BST: Organized binary tree for fast searching (like a sorted phone book)
- Traversals: Different ways to visit all nodes (like different routes through a building)
- Balanced Trees: Self-organizing trees that stay efficient (like a well-managed organization)
Choose the right tree based on what you need to do most often: searching, inserting, or maintaining balance!