Slide 1: Title Slide

Title: Basic Trees - Introduction to Hierarchical Data Structures

Subtitle: Understanding Tree Terminology, Properties & Types
Course: Data Structures

Slide 2: Learning Objectives

• Define what a tree is

• Understand tree terminology (root, parent, child, leaf, etc.)

• Differentiate trees from other data structures (arrays, linked lists)

• Calculate height, depth, level of nodes

• Understand tree properties and formulas

Slide 3: Why Learn Trees?

• Trees represent hierarchical relationships (not possible with arrays/lists)

• Used in: file systems, HTML DOM, network routing, AI decision trees

• Foundation for more advanced structures (BST, AVL, Heap, Trie)

Slide 4: Real-World Tree Examples

Example Tree Structure

Family tree Ancestors → descendants

Company hierarchy CEO → Managers → Employees

File system Root folder → subfolders → files

Website navigation Home → Categories → Pages

Tournament bracket Final match → semifinals → quarterfinals

Slide 5: What is a Tree? – Formal Definition

• A tree is a finite set of one or more nodes such that:

1. There is a specially designated node called the root

 2. The remaining nodes are partitioned into subtrees, each of which is also a tree

• This is a recursive definition

Slide 6: Tree vs. Other Data Structures

Feature Array Linked List Tree

Organization Linear Linear Hierarchical

Insertion/Deletion Slow (O(n)) Fast (O(1) at head) Moderate

Search speed O(n) or O(log n) O(n) O(log n) avg

Memory Contiguous Non-contiguous Non-contiguous

Slide 7: Tree Terminology – Node

• Node: Basic unit of a tree containing data

• Each node can have:

o A value/data

o References (pointers) to child nodes

Slide 8: Tree Terminology – Root

• Root: Topmost node of the tree

• Only node with no parent

• Every tree has exactly one root

• Path from root to any node is unique

(Diagram: Root at top, arrows pointing downward)

Slide 9: Tree Terminology – Parent and Child

• Parent: Node that has one or more nodes directly under it

• Child: Node directly under another node

• Relationship: Parent → Child

• A node can have only one parent (unlike graphs)

Slide 10: Tree Terminology – Siblings

• Siblings: Nodes that share the same parent

• Example: Two child folders inside the same parent folder

• All children of a parent are siblings to each other

(Diagram: Parent P with children A, B, C → A,B,C are siblings)

Slide 11: Tree Terminology – Leaf (External Node)

• Leaf: Node with no children

• Also called terminal node or external node

• Leaves are at the bottom of the tree

• Example: In a file system, files are leaves (folders can have children)

Slide 12: Tree Terminology – Internal Node

• Internal node: Node that has at least one child

• Root can be internal (if tree has >1 node)

• All non-leaf nodes are internal nodes

• Example: Folders containing other folders

Slide 13: Tree Terminology – Edge

• Edge: Connection between two nodes (parent to child)

• A tree with N nodes has exactly N-1 edges

• Reason: Each node except root has exactly one parent edge

Formula: Edges = Nodes – 1

Slide 14: Tree Terminology – Path

• Path: Sequence of nodes and edges from node X to node Y

• Path length = number of edges on the path

• Path from root to any node is unique (no cycles)

• Example: Root → A → B → C (path length = 3)

Slide 15: Tree Terminology – Depth

• Depth of a node: Number of edges from root to that node

• Root depth = 0

• Child of root depth = 1

• Grandchild depth = 2, etc.

(Diagram showing depth levels marked 0,1,2,3)

Slide 16: Tree Terminology – Height

• Height of a node: Number of edges in longest path from that node to a leaf

• Height of leaf = 0

• Height of root = height of tree

• Tree height = maximum depth of any node

Example: Height 3 tree has root-to-leaf path of 3 edges

Slide 17: Tree Terminology – Level

• Level of a node: Depth + 1 (sometimes used interchangeably)

• Root is at Level 1

• Alternative definition: Level = number of nodes on path from root (not edges)

• Be careful: Some books use depth = level

Slide 18: Tree Terminology – Subtree

• Subtree: Any node in the tree + all its descendants

• Every node is root of its own subtree

• Subtrees are themselves trees

• Recursive property: Tree = Root + Subtrees

(Diagram: Highlighting a subtree under a specific node)

Slide 19: Tree Terminology – Degree

• Degree of a node: Number of children it has

• Leaf degree = 0

• Degree of a tree: Maximum degree among all nodes

 • Example: If any node has 5 children, tree degree = 5

Slide 20: Tree Terminology – Forest

• Forest: Set of disjoint (separate) trees

• Removing root from a tree produces a forest (all subtrees)

• A forest can be converted to a tree by adding a dummy root

(Diagram: Multiple trees not connected = forest)

Slide 21: Properties of Trees – Formula 1

Property 1: A tree with N nodes has exactly N-1 edges

Proof: Each node except root has exactly one incoming edge (from parent). Root has 0 incoming
edges. Total edges = N-1.

Slide 22: Properties of Trees – Formula 2

Property 2: For a tree with N nodes:

• If degree of tree = d (max children)

• Minimum height = ceiling(log_d(N(d-1)+1)) - 1

• Maximum height = N-1 (skewed tree)

Slide 23: Properties of Trees – Formula 3

Property 3: Sum of degrees of all nodes = 2 × (N-1)

Because each edge contributes to degree count twice (once at parent, once at child - wait, careful:
Actually each edge contributes 1 to parent's degree only. Let me clarify: parent-child relationship.)

Correct: Sum of (out-degrees) = N-1 (each edge contributes to one parent's degree)

Slide 24: Types of Trees – By Degree

Type Description

General Tree Node can have any number of children

Binary Tree Max 2 children per node

Type Description

Ternary Tree Max 3 children per node

N-ary Tree Max N children per node

Slide 25: Types of Trees – By Structure

Type Description

Ordered Tree Order of children matters (left to right)

Unordered Tree Children have no specific order

Skewed Tree Every node has only one child (like a linked list)

Complete Tree All levels filled except possibly last

Slide 27: Tree Representation – Array Representation

• Store nodes in an array

• For node at index i:

o Parent index stored separately

o Children indices stored

• Good for complete trees (like heaps)

• Can waste space for sparse trees

Slide 28: Tree Traversal – Introduction

• Traversal: Process of visiting each node exactly once

• Two main approaches:

1. Depth-First Search (DFS) – go deep first

2. Breadth-First Search (BFS) – level by level

• For general trees, we don't have inorder (that's for binary trees)
Slide 29: Tree Traversal – Preorder (DFS)

Preorder: Visit root → then recursively traverse each child

Algorithm:

text

preorder(node):

if node == null: return

visit(node)

for each child in [Link]:

preorder(child)

Use: Copy tree, print hierarchical structure

Slide 30: Tree Traversal – Postorder (DFS)

Postorder: Traverse children → then visit root

Algorithm:

text

postorder(node):

if node == null: return

for each child in [Link]:

postorder(child)

visit(node)

Use: Delete tree (delete children before parent)

Slide 31: Tree Traversal – Level Order (BFS)

Level Order: Visit nodes level by level (root first, then level 1, level 2, etc.)

Algorithm: Use a queue

1. Enqueue root

2. While queue not empty:

o Dequeue node → visit it

o Enqueue all its children

Use: Shortest path, print tree by levels

Slide 32: Applications of General Trees

Application Description

File system Directory hierarchy (FAT, NTFS, ext4)

HTML/XML DOM Web page element hierarchy

Organizational chart Company structure

Game trees Chess, tic-tac-toe decision trees

Parse trees Compilers (syntax analysis)

Family tree Genealogy research

Slide 33: Advantages and Disadvantages of Trees

Advantages:

• Natural representation of hierarchy

• Faster search/insert/delete than linked lists (on average)

• Flexible size (dynamic)

Disadvantages:

• More complex to implement than arrays/lists

• Memory overhead (pointers)

• No direct access (unlike array index)

• Can become unbalanced

Slide 34: Common Tree Operations & Complexity

Operation Time Complexity

Search O(n) worst case

Insert child O(1) (if parent known)

Operation Time Complexity

Delete subtree O(size of subtree)

Traversal (DFS/BFS) O(n)

Find depth O(n)

Find height O(n)

Slide 35: Practice Questions – Basic Trees

1. A tree has 50 nodes. How many edges does it have? (Ans: 49)

2. If root depth = 0, what is depth of node at level 5? (Ans: 4)

3. Height of leaf = ? (Ans: 0)

4. Can a tree have 2 roots? (Ans: No)

5. What is a forest? (Ans: Collection of disjoint trees)

Slide 36: Summary – Basic Trees

• Tree = hierarchical structure with root, parent-child relationships

• Key terms: root, leaf, edge, path, depth, height, level, degree, subtree

• Properties: N nodes → N-1 edges, unique path between any two nodes

• Traversals: Preorder, Postorder, Level order

• Used everywhere: file systems, DOM, parsing, AI

Slide 1: Title Slide

Title: Hash Tables – Fast Data Retrieval in O(1)

Subtitle: Hash Functions, Collision Resolution (Chaining & Open Addressing)
Course: Data Structures

Slide 2: Learning Objectives

• Understand what a hash table is and why it's used

• Learn what hash functions are and their properties

• Understand collisions and why they happen

• Master collision resolution techniques: Chaining and Open Addressing

• Compare different open addressing strategies (Linear, Quadratic, Double Hashing)

• Analyze time complexity and load factor

Slide 3: The Problem – Fast Searching

Problem: We want to search, insert, delete in O(1) time on average

Data Structure Search Time

Unsorted Array O(n)

Sorted Array (Binary Search) O(log n)

Linked List O(n)

Binary Search Tree (balanced) O(log n)

Hash Table Goal: O(1) average case for all operations!

Slide 4: The Idea Behind Hashing

• Use a hash function to compute an index from a key

• Store the key (or key-value pair) at that index in an array

• To search: compute index → go directly to that position

• Direct addressing – like an array but with any key type

Analogy: Library where book title determines exact shelf number

Slide 5: What is a Hash Table?

• A data structure that implements an associative array (key → value)

• Also called: HashMap, Dictionary, Map, Symbol Table

• Components:

1. An array of fixed size (table)

2. A hash function h(key) → index (0 to M-1)

Slide 6: Hash Table – Basic Example

Store phone numbers using name as key:

Key (Name) Hash Function (sum of letters % 10) Index Value (Phone)

"Alice" (1+12+9+3+5) % 10 = 30 % 10 = 0 0 555-1234

"Bob" (2+15+2) % 10 = 19 % 10 = 9 9 555-5678

Array of size 10: index 0 stores Alice, index 9 stores Bob.

Slide 7: Hash Table Operations

Insert(key, value):

1. Compute index = h(key)

2. Store (key, value) at table[index]

Search(key):

1. Compute index = h(key)

2. Return value at table[index]

Delete(key):

1. Compute index = h(key)

2. Remove entry at table[index]

All operations take O(1) time if no collision!

Slide 8: What is a Hash Function?

• A function that maps any key to an integer index within table range
 • h(key) → {0, 1, 2, ..., M-1} where M = table size

Slide 9: Properties of a Good Hash Function

1. Deterministic: Same key always gives same index

2. Fast to compute: O(1) time

3. Uniform distribution: Spreads keys evenly across table

4. Minimize collisions: Different keys rarely map to same index

5. Use all table slots: No bias toward certain indices

Slide 10: Hash Function – Division Method

Formula: h(k) = k mod M

Example: M = 10, keys: 25, 37, 42, 18

• 25 % 10 = 5

• 37 % 10 = 7

• 42 % 10 = 2

• 18 % 10 = 8

Choice of M matters:

• Avoid powers of 2 (bad distribution)

• Best: prime number not close to power of 2

Slide 14: The Collision Problem

Collision: Two different keys map to the same index

Example: M=10

• h(25) = 5

• h(35) = 5 ← Collision!

Collisions are unavoidable (pigeonhole principle):

• More possible keys than table slots

• Birthday paradox: collisions happen sooner than expected

Slide 15: Collision Resolution – Two Main Approaches

Method Description

Chaining Each table slot points to a linked list of entries

Open Addressing Find another empty slot within the table

Both have trade-offs in performance and memory.

PART A: CHAINING (Separate Chaining)

Slide 16: Chaining – Concept

• Each slot in hash table is a linked list (or other container)

• When collision occurs, append new key to the list at that slot

• All keys that hash to same index are stored together

Visual:

text

Index: 0 → [key1, val1] → [key2, val2] → null

1 → null

2 → [key3, val3] → null

...

Slide 22: Chaining – Time Complexity

Operation Average Worst Case

Insert O(1) O(n) (all keys in same slot)

Operation Average Worst Case

Search O(1 + α) O(n)

Delete O(1 + α) O(n)

Worst case: Poor hash function puts all keys in one slot

Slide 23: Chaining – Advantages & Disadvantages

Advantages:

• Simple to implement

• Table never fills up (can keep growing)

• Easy deletion

• Performance degrades gracefully

Disadvantages:

• Extra memory for pointers

• Cache performance poor (linked lists scattered in memory)

• Worst case still O(n)

Slide 24: Chaining – Alternatives to Linked Lists

Instead of linked lists, use:

• Dynamic arrays (better cache locality)

• Balanced BST (O(log n) worst case per slot)

• Another hash table (recursive hashing)

Java's HashMap uses linked lists until threshold, then converts to Red-Black Tree (balanced BST)

PART B: OPEN ADDRESSING

Slide 25: Open Addressing – Concept

• All elements stored inside the array itself (no external lists)

• When collision occurs, probe (search) for next empty slot

• Table can get full (unlike chaining)

 • Requires deletion markers (tombstones)

Advantage: Reduces primary clustering

Disadvantage: Secondary clustering (same hash leads to same probe path)

Slide 37: Chaining vs Open Addressing – Comparison

Feature Chaining Open Addressing

Table size Can exceed M Never exceeds M

Memory Extra for pointers No extra pointers

Deletion Easy (just remove) Hard (tombstones needed)

Performance at α>1 Graceful Fails (full table)

Cache performance Poor (linked lists) Good (contiguous array)

Worst case O(n) O(n) but sooner

Slide 40: Applications of Hash Tables

Application Description

Database indexing Fast record lookup

Caches (memcached, Redis) Key-value storage

Symbol tables (compilers) Variable name → info

Spell checkers Dictionary lookup

Password storage Store hashed passwords

Cryptography Hash functions (SHA, MD5)

Application Description

Message deduplication Detect duplicate data

Slide 41: Hash Table Time Complexity Summary

Operation Average Case Worst Case Amortized

Insert O(1) O(n) O(1)

Search O(1) O(n) O(1)

Delete O(1) O(n) O(1)

Rehash O(n) O(n) O(1) per insert

Worst case happens with bad hash function or adversarial input