Tree Data Structures

🌳 Hierarchical Organization: Family Trees for Data

Master hierarchical data organization with binary trees and search trees

1 Why Do We Need Trees?

🌍 Real-World Problems

📁 File Systems: Directories and subdirectories form a tree structure
🔍 Database Indexing: B-trees enable fast data retrieval
🌐 DOM Structure: HTML elements form a tree in web pages
🧮 Expression Parsing: Mathematical expressions as parse trees

Hierarchical Organization

Trees provide natural ways to organize hierarchical data with efficient search, insertion, and deletion operations. They're fundamental to many computer science algorithms and data structures.

2 Mental Model: Family Tree

🌳 Think of Trees Like a Family Tree

👑
Root Node

Like the oldest ancestor - the starting point of the family tree

👨‍👩‍👧‍👦
Parent-Child Relationships

Like family relationships - each person has one parent (except root)

🍃
Leaf Nodes

Like family members with no children - the endpoints of branches

📏
Height/Depth

Like generations - how many levels from root to furthest descendant

3 Tree Fundamentals

🌳 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   5

📊 Binary Search Tree (BST)

A tree where left children are smaller and right children are larger than their parent

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)

4 Hands-on Practice: Build Your Tree

🌳 Tree Visualization

Insert nodes to build your binary search tree!

📊 Tree Traversals

In-order: []
Pre-order: []
Post-order: []
Tree Height: 0
Node Count: 0

5 Tree Traversal: Visiting All Nodes

🚶‍♂️ In-order Traversal

Visit left subtree, root, then right subtree. For BST, this gives sorted order!

def inorder_traversal(node):
    result = []
    if node:
        result.extend(inorder_traversal(node.left))
        result.append(node.value)
        result.extend(inorder_traversal(node.right))
    return result

# For BST: [4, 2, 5, 1, 3] becomes [1, 2, 3, 4, 5]

🏃‍♂️ Pre-order & Post-order

Different visiting patterns for different use cases

# Pre-order: Root, Left, Right
def preorder_traversal(node):
    result = []
    if node:
        result.append(node.value)
        result.extend(preorder_traversal(node.left))
        result.extend(preorder_traversal(node.right))
    return result

# Post-order: Left, Right, Root
def postorder_traversal(node):
    result = []
    if node:
        result.extend(postorder_traversal(node.left))
        result.extend(postorder_traversal(node.right))
        result.append(node.value)
    return result

6 Critical Pitfall: Unbalanced Trees

⚠️ The Degenerate Tree Trap

If you insert sorted data into a BST, it becomes a linear chain, losing all the benefits of tree structure!

❌ Wrong: Inserting Sorted Data

# 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
#      \
#       4  (and so on...)

# Search time: O(n) instead of O(log n)!
💥 Result: O(n) search time, no better than a linked list

✅ Right: Insert in Random Order or Use Balanced Trees

# 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:
#       4
#      / \
#     2   6
#    / \ / \
#   1  3 5  7

# Search time: O(log n)
✅ Result: O(log n) search time, efficient tree operations

7 Knowledge Assessment: Tree Mastery

Question 1: BST Property

In a Binary Search Tree, what is the key property that must be maintained?

Question 2: Tree Traversal

Which traversal method gives nodes in sorted order for a BST?

Question 3: Balanced vs Unbalanced

What happens when you insert sorted data (1,2,3,4,5) into an empty BST?

Mastery Progress: 0%