DATA STRUCTURES AND
ALGORITHMS
SCS 3102
George William Kasaazi
Module 5: Non-Linear Data Structures
• Recap: In previous modules, we covered Linear data
structures. In these, each element has a clear "before" and
"after".
• Any Limitations?
• The real world is rarely so simple. How would you represent:
• An organization's management structure?
• The folders and files on your computer's hard drive?
• A family tree?
• Linear structures are a poor fit for
these hierarchical relationships. We need a new tool.
Introduction to Trees
• Definition: A Tree is a non-linear data structure that
consists of a collection of nodes connected by edges,
organized in a hierarchical fashion.
• Key Characteristics:
• There is one special node called the Root, which is the starting
point of the tree.
• Every node (except the root) is connected by an edge from exactly
one other node. This node is called its Parent.
• A node can be connected to zero or more other nodes. These are
called its Children.
• Crucially, there are no cycles. You can't follow a path of edges
and end up back where you started.
Core Tree Terminology
• Root: The top-most node of the tree. The only node with no parent.
• Parent: A node that has at least one child.
• Child: A node that has a parent.
• Siblings: Nodes that share the same parent.
• Leaf: A node with no children. These are the endpoints of the tree.
• Edge: The link between a parent and its child.
• Path: A sequence of nodes and edges connecting a node with a
descendant.
• Height of a Tree: The length of the longest path from the root to
any leaf.
• Depth of a Node: The length of the path from the root to that node.
Recursive data structure
• Recursive definition: A tree is either:
• empty (null), or
• a root node that contains:
• data,
• a left tree, and
• a right tree
A tree node for integers
• A basic tree node object stores data, refers to left/right
• Multiple nodes can be linked together into a larger tree
Binary Trees
• While a node in a general tree can have any number of children, the
most common and important type of tree in computer science is
the Binary Tree.
• Definition: A Binary Tree is a tree where each node can have at
most two children.
• These children are given specific names: the left child and the right
child.
• This simple constraint makes the data structure much easier to
implement and analyze.
Key Characteristics
• Nodes
• Each node in a binary tree typically contains a value or key, and pointers
or references to its left and right children.
• Root
• The topmost node in a binary tree is called the root.
• Leaves
• Nodes with no children are called leaf nodes or leaves.
• Hierarchy
• The structure is hierarchical, with parent-child relationships between
nodes.
• Ordered
• Elements in binary trees are often stored in an ordered manner,
especially in variations like Binary Search Trees.
The Binary Search Tree (BST)
• A regular Binary Tree has no rules about where data is
placed.
• A Binary Search Tree (BST) imposes one critical rule that
makes it incredibly efficient for searching:
• The BST Property: For any given node N in the tree:
• All values in N's left subtree must be less than N's value.
• All values in N's right subtree must be greater than N's value.
• This property combines the fast O(log n) searching of a
sorted array with the fast O(1) insertion/deletion flexibility
of a linked structure.
Searching a BST
The BST property allows us to search with extreme efficiency.
The algorithm is very similar to Binary Search in an array.
• Start at the root.
• Compare the target value with the current node's value.
• If target < current, you know the value (if it exists) MUST
be in the left subtree. Ignore the right half completely.
• If target > current, you know the value MUST be in
the right subtree. Ignore the left half.
• If target == current, you've found it!
• If you reach a nullptr, the value does not exist in the tree.
C++ Implementation:
The TreeNode
The TreeNode and and
struct is pointer-based BST
holdsClass
the data, along with left and right
pointers. The BST class manages the root pointer and prevents memory leaks.
#include <iostream>
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
class BST {
private:
TreeNode* root;
// ... private helper methods for recursion will go here ...
public:
BST() : root(nullptr) {}
~BST(); // A proper destructor is vital!
void insert(int value);
bool search(int value);
};
BST Class: Recursive Insertion
// Inside the BST class
private:
TreeNode* insertHelper(TreeNode* node, int value) {
// Base case: If we've found an empty spot, create the new node here.
if (node == nullptr) {
return new TreeNode(value);
}
// Recursive step: Go down the tree
if (value < node->data) {
node->left = insertHelper(node->left, value);
} else if (value > node->data) {
node->right = insertHelper(node->right, value);
}
// If value already exists, do nothing and return the unchanged node.
return node;
}
public:
void insert(int value) {
root = insertHelper(root, value);
}
BST Visualization
BST Analysis
Time Complexity (Search, Insert, Delete):
Best/Average Case: O(log n).
This happens when the tree is balanced (the left and
right subtrees have roughly the same height). In this case,
every comparison halves the search space.
Worst Case: O(n).
This happens when the tree
is unbalanced or degenerate. For example, if you insert
sorted numbers (10, 20, 30, 40...), the tree becomes just a
single long chain to the right. It behaves exactly like
a Linked List.
Tree Traversal
Definition: A traversal is a systematic process of "visiting"
(e.g., printing or processing) every single node in a tree
exactly once.
An examination of the elements of a tree.
A pattern used in many tree algorithms and methods
• Pre-order
• process root node, then its left/right subtrees
• In-order
• process left subtree, then root node, then right
• Post-order
• process left/right subtrees, then root node
Tree Traversal Methods
pre-order
17 41 29 6 9 81 40
in-order
29 41 6 17 81 9 40
post-order
29 6 41 81 40 9 17
Pre-order Traversal (Visualization)
In-order Traversal (Visualization)
Post-order Traversal (Visualization)
Beyond Trees: Introducing Graphs
What if a node could have multiple parents?
What if there were cycles?
Then it's no longer a tree—it's a Graph.
Definition: A Graph is a data structure consisting of a set
of vertices (nodes) and a set of edges (links) that connect pairs of
vertices.
It is the ultimate tool for modeling networks: social networks, road
maps, computer networks, etc.
Core Graph Terminology
Vertex (or Node)
Represents an entity (e.g., a person, a city).
Edge (or Link)
Represents a connection between two vertices.
Undirected Graph
Edges have no direction. If A is connected to B, B is connected to A (e.g.,
Facebook friendship).
Directed Graph (Digraph)
Edges have a direction. A connection from A to B does not imply a
connection from B to A (e.g., following someone on Twitter).
Weighted Graph
Each edge is assigned a "weight" or "cost" (e.g., the distance between two
cities on a map).
Representing Graphs in Code
There are two primary ways to store the connections in a
graph:
Adjacency Matrix
• A 2D V x V array matrix where matrix[i][j] = 1 if there's an edge
from vertex i to j.
• Pro: O(1) time to check if an edge exists.
• Con: Uses O(V²) memory, which is very wasteful for sparse graphs
(graphs with few edges).
Adjacency List (Most Common)
• An array of linked lists. The i-th list contains all the vertices
adjacent to vertex i.
• Pro: Very memory-efficient for sparse graphs, using O(V + E)
A Special Tree for Disks: The B-Tree
• Definition: A B-Tree is a self-balancing search tree where
nodes can have many children (far more than two).
• Main Use Case: Databases and filesystems.
• Why is it useful? Reading data from a spinning hard disk
is extremely slow compared to reading from RAM. A B-Tree
is optimized to minimize disk reads.
• By having "fat" nodes (many keys and many child pointers), the
tree is very "short".
• Finding a piece of data might require traversing only 4 or 5 levels,
even in a database with billions of records. This means only 4 or 5
disk reads, which is very fast.
End of Module Practice Questions
Theoretical Questions
What is the single most important property that differentiates a Tree from a Graph?
What is the BST Property and why is it essential for efficient searching?
Explain the worst-case scenario for a Binary Search Tree's performance. What does the tree look like in
this case?
If you perform an In-Order traversal on a valid BST, what will be the order of the nodes you visit?
What is the primary motivation for using a B-Tree instead of a BST in a database system?
Analytical Questions
Given the following numbers to be inserted into an empty BST in this order: 50, 20, 70, 10, 30, 60, 80,
25. Draw the resulting BST.
Using the BST you drew in the previous question, write down the sequence of nodes visited for:
a) Pre-Order Traversal
b) In-Order Traversal
c) Post-Order Traversal
You are modeling a city's road network for a GPS. Would you use a directed or undirected graph? A
End of Module Practice Questions
Practical Coding Exercises
Enhance the BST Class
Implement a destructor for the BST class we designed. It must use a Post-Order
traversal to delete all nodes and prevent memory leaks.
Implement a method int findMin() that finds and returns the smallest value in the
BST. (Hint: Which way do you always go from the root?).
Graph Representation
Write a simple C++ class Graph that uses an Adjacency List to represent an
unweighted, undirected graph. Use std::vector<std::list<int>> for the underlying
storage.
Provide the following methods:
Graph(int numVertices): Constructor.
void addEdge(int u, int v): Adds an edge between vertices u and v.
void printGraph(): Prints the adjacency list for each vertex.
In main, create a graph and add a few edges to test your implementation.