Week # 9

11.1 Introduction to Trees

1. Introduction
In the previous chapter, we studied how graphs help us model real-life problems.​
In this chapter, we focus on a special type of graph called a tree.
Trees are extremely important in computer science because:

●​ They help create fast searching algorithms (e.g., binary search trees).
●​ They are used in data compression (Huffman coding).
●​ Trees are used to model decision-making processes (e.g., game trees in
chess).
●​ They help design minimum-cost networks (e.g., telephone or internet
networks).
●​ Algorithms like Depth-First Search (DFS) and Breadth-First Search (BFS)
build trees to explore graphs.

Trees also appear in everyday life—for example, family trees, where people are
connected through parent–child relationships.
Connected Graph (Basic Definition)
Before defining a tree, we need the idea of a connected graph.

Connected Graph

An undirected graph is connected if there is a path between every pair of

vertices.

If even one vertex is unreachable from another, the graph is not connected.

Example:

●​ If you can go from every city to every other city using roads → connected
graph.
●​ If some cities are isolated → not connected.

Tree

A tree is a connected, undirected graph that contains no simple circuits.

In easy words:

●​ All vertices are connected → no isolated part

●​ No loops or repeated cycles → no “round trips”
●​ Looks like a branching structure

Because trees cannot contain loops or repeated edges, every tree is a simple
graph.
G1: Connected and has no circuits → ✔ Tree

G2: Connected and has no circuits → ✔ Tree

G3: Has a simple circuit → ✘ Not a tree​

e-b-a-d-e

G4: Not connected → ✘ Not a tree

A-f and c-e-b-d

Forest

A forest is an undirected graph with no simple circuits, but it does not have to
be connected.

Each connected part of a forest is itself a tree.

You can think of a forest as “a collection of trees.”

What Is a Rooted Tree?

In many applications, we take a normal tree (an undirected, connected graph

with no cycles) and choose one special vertex to be the root.

Once we choose a root:

●​ Every edge is considered to be directed away from the root.

●​ This gives us a directed structure, useful in computer science for
hierarchical data.

Definition: Rooted Tree

A rooted tree is a tree in which:

1.​ One vertex is designated as the root, and

2.​ Every edge is directed away from the root.

Even though the edges have directions, we normally do not draw arrowheads,
because the root already determines the direction.
Unrooted vs. Rooted Trees
Any tree can be turned into a rooted tree by choosing any vertex as the root.

Different choices of root give different rooted trees.

●​ If a is the root → edges flow away from a

●​ If c is the root → the tree looks different

We usually draw the root at the top.

Family Terminology in a Rooted Tree

Once the tree has a root, we can talk about:

Parent
If there is an edge from u → v, then​
u is the parent of v.

Child
If u is the parent of v, then​
v is the child of u.

Siblings
Children with the same parent.

Ancestor

For any vertex v (except the root):

​
Its ancestors = all vertices on the path from the root to v​
(excluding v itself but including the root).

Descendants
Vertices that come below a vertex.

Leaf
A vertex with no children.

Internal Vertex
A vertex that has at least one child.

(Except if the tree has only 1 vertex, then the root is also a leaf.)

Subtree

The subtree rooted at a vertex a consists of:

●​ The vertex a
●​ All of its descendants
●​ The edges connecting them

EXAMPLE 2: In the rooted tree T (with root a) shown in Figure 5, find the parent
of c, the children of g, the siblings of h, all ancestors of e, all descendants of b, all
internal vertices, and all leaves. What is the subtree rooted at g?
Solution:

Parent of c → b
Children of g → h, i, j ​
Siblings of h → i and j​
Ancestors of e → c, b, a​
Descendants of b → c, d, e​
Internal vertices → a, b, c, g, h, j​
Leaves → d, e, f, i, k, l, m​
Subtree rooted at g → vertices {g, h, i, j, k, l, m} and related edges

m-ary Trees
Many computer algorithms use trees where every internal vertex has a fixed
number of children.

m-ary Tree

A rooted tree is an m-ary tree if every internal vertex has ≤ m children.

Full m-ary Tree

A tree is a full m-ary tree if every internal vertex has exactly m children.

Special case:

●​ m = 2 → Binary Tree
EXAMPLE 3: Are the rooted trees in Figure 7 full m-ary trees for some positive
integer m?

T1: Every internal vertex has exactly 2 children → Full binary tree

T2: Every internal vertex has exactly 3 children → Full 3-ary tree

T3: Every internal vertex has exactly 5 children → Full 5-ary tree

❌
T4: Some internal vertices have 2 children, some have 3 →​
Not full m-ary tree

Ordered Rooted Trees

In many applications, the order of children matters.

Ordered Rooted Tree

A rooted tree where children are arranged in a left-to-right order.

This order is shown naturally in diagrams, even without arrows.

Special Case: Ordered Binary Tree

Often simply called a binary tree.

●​ First child = left child

●​ Second child = right child

Left and Right Subtrees. For any vertex:

 ●​ The tree at its left child → left subtree
●​ The tree at its right child → right subtree​

EXAMPLE 4: What are the left and right children of d in the binary tree T shown
in Figure 8(a) (where the order is that implied by the drawing)? What are the left
and right subtrees of c?

Solution:

Left child of d → f

Right child of d → g

Left subtree of c → shown in Figure 8(b)

Right subtree of c → shown in Figure 8(c)

12.1 Boolean Functions

Computers and digital circuits operate only with 0 and 1.​
Boolean algebra is a mathematical system that tells us how to combine 0s and
1s using the rules of logic.

Claude Shannon (1938) showed that Boolean algebra = the language of digital
circuits. So

●​ Boolean algebra → expressions with 0/1

●​ Boolean functions → outputs of circuits
 ●​ Boolean identities → rules for simplifying circuits
●​ Karnaugh maps + Quine–McCluskey → methods to minimize circuits

Operations in Boolean Algebra

1. Complement (NOT)

●​ 0' = 1
●​ 1' = 0​
(This means “reverse the value.”)

Order of Operations
Like BODMAS in arithmetic, Boolean algebra has a priority:

1.​ NOT (complement)

2.​ AND (product)
3.​ OR (sum)

Boolean Expression → Logical Expression

Boolean algebra uses 0,1,+,·, and complement.​

Logic uses F, T, ∨, ∧, and ¬.

Example:​
1·0 + (0+1) → (T ∧ F) ∨ ¬(F ∨ T)

Exactly the same meaning.

Boolean Expressions and Boolean Functions

Boolean Expressions

Boolean functions can be represented using expressions made up from variables

and Boolean operations.

Example:
12.3 Logic Gates
Boolean algebra is a special kind of mathematics where the values are only:

●​ 0 (OFF, FALSE)
●​ 1 (ON, TRUE)

It is used to design electronic circuits inside computers, calculators, mobile

phones, and many other digital devices.

Each circuit takes inputs (0 or 1) and produces an output (0 or 1) based on rules

of Boolean algebra.
Gates

A gate is a basic building block of a digital circuit.​

Each gate performs a Boolean operation such as NOT, OR, AND.

The circuits we study in this chapter are:

●​ Combinational circuits
●​ They have no memory
●​ Output depends ONLY on the current inputs

So these circuits cannot store information—whatever you give as input, they

immediately give the output.

Gates with Many Inputs

You can have three, four, or even more inputs for both AND and OR gates.

Examples:
Combinations of Gates

Combinational circuits can be constructed using a combination of inverters, OR

gates, and AND gates. When combinations of circuits are formed, some gates
may share inputs.

We can connect NOT, OR, and AND gates together to make bigger circuits that
perform more complex tasks.