2 of 68

11.1 Introduction to TREE �and its Terminologies

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

Graph VS TREE

3 of 68

Trees

Definition: A tree is a connected undirected graph with no simple circuits.

Definition: An undirected graph is a tree if and only if there is a unique simple path between any two of its vertices. A tree cannot contain multiple edges or loops.

Definition: An undirected graph is a tree if and only if there is a unique simple path between any two of its vertices.

4 of 68

Trees

Example: Which of these graphs are trees?

Solution: G₁ and G₂ are trees - both are connected and have no simple circuits. G₃ is not a tree because e, b, a, d, e is a simple circuit,. G₄ is not a tree because it is not connected.

5 of 68

Forest

Definition: A forest is a graph that has no simple circuit, but is not connected. Each of the connected components in a forest is a tree.

6 of 68

General form of TREEs

7 of 68

Applications of Trees

Section 11.2

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

8 of 68

Trees as Models

Trees are used as models in computer science, chemistry, geology, botany, psychology, and many other areas.

Trees were introduced by the mathematician Cayley in 1857 in his work counting the number of isomers of saturated hydrocarbons. The two isomers of butane are:.

Arthur Cayley

(1821-1895)

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

9 of 68

Trees as Models

The organization of a computer file system into directories, subdirectories, and files is naturally represented as a tree.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

10 of 68

Trees as Models

Trees are used to represent the structure of organizations.

11 of 68

Applications of Trees

Game Trees

Trees can be used to analyze certain types of games such as tic-tac-toe, nim, checkers, and chess.

12 of 68

Universal Address Systems

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

13 of 68

Prefix code

Definition: A code that has the property that the code of a character is never a prefix of the code of another character.

A prefix code can be represented using a binary tree, where the characters are the labels of the leaves in the tree.
The edges of the tree are labeled so that an edge leading to a left child is assigned a 0 and an edge leading to a right child is assigned a 1.
The bit string used to encode a character is the sequence of labels of the edges in the unique path from the root to the leaf that has this character as its label.
For instance, the tree in Figure 5 represents the encoding of e by 0, a by 10, t by 110, n by 1110, and s by 1111.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

14 of 68

Huffman Coding

Huffman code is a way to encode information using variable-length strings to represent symbols depending on how frequently they appear. The idea is that symbols that are used more frequently should be shorter while symbols that appear more rarely can be longer.

15 of 68

Decision Trees

Definition: A rooted tree where each vertex represents a possible outcome of a decision and the leaves represent the possible solutions of a problem.

Rooted trees can be used to model problems in which a series of decisions leads to a solution.
The possible solutions of the problem correspond to the paths to the leaves of this rooted tree.

Example : A decision tree that orders the elements of the list a, b, c.

16 of 68

Rooted Trees

Definition: A rooted tree is a tree in which one vertex has been designated as the root and every edge is directed away from the root.

An unrooted tree is converted into different rooted trees when different vertices are chosen as the root.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

17 of 68

Rooted Tree Terminology

Terminology for rooted trees is a mix from botany and genealogy (such as this family tree of the Bernoulli family of mathematicians).

18 of 68

Rooted Tree Terminology

If v is a vertex of a rooted tree other than the root, the parent of v is the unique vertex u such that there is a directed edge from u to v. When u is a parent of v, v is called a child of u. Vertices with the same parent are called siblings.

19 of 68

Rooted Tree Terminology

The ancestors of a vertex are the vertices in the path from the root to this vertex, excluding the vertex itself and including the root.
The descendants of a vertex v are those vertices that have v as an ancestor. The subtree rooted at u includes all the descendants of u, and all edges that connect between them.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

20 of 68

Rooted Tree Terminology

A vertex of a rooted tree with no children is called a leaf. Vertices that have children are called internal vertices.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

21 of 68

Terminology for Rooted Trees

Example: In the rooted tree T (with root a):

Find the parent of c, the children of g, the siblings of h, the ancestors of e, and the descendants of b.

Solution:

The parent of c is b. The children of g are h, i, and j. The siblings of h are i and j. The ancestors of e are c, b, and a. The descendants of b are c, d, and e.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

22 of 68

Terminology for Rooted Trees

Example: In the rooted tree T (with root a):

Find all internal vertices and all leaves.

Solution:

The internal vertices are a, b, c, g, h, and j. The leaves are d, e, f, i, k, l, and m.

23 of 68

Terminology for Rooted Trees

What is the subtree rooted at g?

Solution:

We display the subtree rooted at g.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

24 of 68

Level of vertices and height of trees

When working with trees, we often want to have rooted trees where the sub trees at each vertex contain paths of approximately the same length.
To make this idea precise we need some definitions:

The level of a vertex v in a rooted tree is the length of the unique path from the root to this vertex.
The height of a rooted tree is the maximum of the levels of the vertices.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

25 of 68

Level of vertices and height of trees

Example:

(i) Find the level of each vertex in

the tree to the right.

(ii) What is the height of the tree?

Solution:

(i) The root a is at level 0.

Vertices b, j, and k are at level 1.

Vertices c, e, f, and l are at level 2.

Vertices d, g, i, m, and n are at level 3.

Vertex h is at level 4.

(ii) The height is 4, since 4 is the largest level of any vertex.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

26 of 68

m-ary Rooted Trees

Definition: A rooted tree is called an m-ary tree if every internal vertex has no more than m children. The tree is called a full m-ary tree if every internal vertex has exactly m children. An m-ary tree with m = 2 is called a binary tree.

Example: Are the following rooted trees full m-ary trees for some positive integer m?

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

27 of 68

Solution:

T₁ is a full binary tree because each of its internal vertices has two children.
T₂is a full 3-ary tree because each of its internal vertices has three children.
In T₃ each internal vertex has five children, so T₃ is a full

5-ary tree.

T₄is not a full m-ary tree for any m because some of its internal vertices have two children and others have three children.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

28 of 68

Balanced m-Ary Trees

Definition: A rooted m-ary tree of height h is balanced if all leaves are at levels h or h − 1.

Example: Which of the rooted trees shown below is balanced?

Solution: T₁ and T₃ are balanced, but T₂ is not because it has leaves at levels 2, 3, and 4.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

29 of 68

Ordered Rooted Trees

Definition: An ordered rooted tree is a rooted tree where the children of each internal vertex are ordered.

We draw ordered rooted trees so that the children of each internal vertex are shown in order from left to right.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

30 of 68

Binary Trees

Definition: A binary tree is an ordered rooted where each internal vertex has at most two children. If an internal vertex of a binary tree has two children, the first is called the left child and the second the right child. The tree rooted at the left child of a vertex is called the left subtree of this vertex, and the tree rooted at the right child of a vertex is called the right subtree of this vertex.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

31 of 68

Example:

Consider the binary tree T.

(i) What are the left and right children of d?

(ii) What are the left and right sub trees of c?

Solution:

(i) The left child of d is f and the right child is g.

(ii) The left and right subtrees of c are displayed in (b) and (c).

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

32 of 68

Properties of Trees

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

33 of 68

Binary Search Tree

Definition: A binary tree in which the vertices are labeled with items so that a label of a vertex is greater than the labels of all vertices in the left subtree of this vertex and is less than the labels of all vertices in the right subtree of this vertex.

Searching for items in a list is one of the most important tasks that arises in computer science.
Our primary goal is to implement a searching algorithm that finds items efficiently when the items are totally ordered. This can be accomplished through the use of a binary search tree.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

34 of 68

Example : Form a binary search tree for the words mathematics, physics, geography, zoology, meteorology, geology, psychology, and chemistry (using alphabetical order).

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

35 of 68

Tree Traversal

Section 11.3

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

36 of 68

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

Traversal Algorithms Procedures for systematically visiting every vertex of an ordered rooted tree are called traversal algorithms. We will describe three of the most commonly used such algorithms, preorder traversal, inorder traversal, and postorder traversal.

11.3 Tree Traversal

37 of 68

Tree Traversal Shortcut Preorder:

Inorder:

Postorder:

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

38 of 68

Tree Traversal

Definition: Let T be an ordered rooted tree with root r. If T consists only of r, then r is the preorder traversal of T. Otherwise, suppose that T₁, T₂, …, T_n are the subtrees of r from left to right in T. The preorder traversal begins by visiting r, and continues by traversing T₁ in preorder, then T₂ in preorder, and so on, until T_n is traversed in preorder.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

39 of 68

Inorder traversal: Visit leftmost subtree, visit root, visit other subtrees left to right

40 of 68

Inorder Traversal

Definition: Let T be an ordered rooted tree with root r. If T consists only of r, then r is the inorder traversal of T. Otherwise, suppose that T₁, T₂, …, T_n are the subtrees of r from left to right in T. The inorder traversal begins by traversing T₁ in inorder, then visiting r, and continues by traversing T₂ in inorder, and so on, until T_n is traversed in inorder.

41 of 68

Inorder traversal:

Visit leftmost subtree,

visit root, visit other

subtrees left to right

42 of 68

Postorder Traversal

Definition: Let T be an ordered rooted tree with root r. If T consists only of r, then r is the postorder traversal of T. Otherwise, suppose that T₁, T₂, …, T_n are the subtrees of r from left to right in T. The postorder traversal begins by traversing T₁ in postorder, then T₂ in postorder, and so on, after T_n is traversed in postorder, r is visited.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

43 of 68

Postorder traversal:

Visit subtrees left to right;

visit root

44 of 68

Infix, Prefix, and Postfix Notation �Expression Trees

Complex expressions can be represented using ordered rooted trees.
Consider the expression ((x + y) ↑ 2 ) + ((x − 4)/3).
A binary tree for the expression can be built from the bottom up, as is illustrated here.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

45 of 68

Infix Notation

An inorder traversal of the tree representing an expression produces the original expression when parentheses are included except for unary operations, which now immediately follow their operands.
We illustrate why parentheses are needed with an example that displays three trees all yield the same infix representation.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

46 of 68

Tree Traversal Shortcut Preorder:

Inorder:

Postorder:

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

47 of 68

Deep Understanding

(x + y) / (x + 3)

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

48 of 68

Prefix Notation

When we traverse the rooted tree representation of an expression in preorder, we obtain the prefix form of the expression. Expressions in prefix form are said to be in Polish notation, named after the Polish logician Jan Łukasiewicz.
Operators precede their operands in the prefix form of an expression. Parentheses are not needed as the representation is unambiguous.
The prefix form of ((x + y) ↑ 2 ) + ((x − 4)/3)

is + ↑ + x y 2 / − x 4 3.

Prefix expressions are evaluated by working from right to left. When we encounter an operator, we perform the corresponding operation with the two operations to the right.

Jan Łukasiewicz (1878-1956)

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

49 of 68

Prefix Notation

Example: We show the steps used to evaluate a particular prefix expression:

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

50 of 68

Postfix Notation

We obtain the postfix form of an expression by traversing its binary trees in postorder. Expressions written in postfix form are said to be in reverse Polish notation.
Parentheses are not needed as the postfix form is unambiguous.
x y + 2 ↑ x 4 − 3 / + is the postfix form of ((x + y) ↑ 2 ) + ((x − 4)/3).
A binary operator follows its two operands. So, to evaluate an expression one works from left to right, carrying out an operation represented by an operator on its preceding operands.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

51 of 68

Postfix Notation

Example: We show the steps used to evaluate a particular postfix expression.

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

52 of 68

Spanning Trees

Section 11.4

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

53 of 68

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected.

By this definition, we can draw a conclusion that every connected and undirected Graph G has at least one spanning tree. A disconnected graph does not have any spanning tree, as it cannot be spanned to all its vertices.

Spanning Tree

54 of 68

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

55 of 68

Kirchhoff's Matrix tree theorem

56 of 68

Understanding Minimum spanning tree

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

A minimum spanning tree is a spanning tree in which the sum of the weight of the edges is as minimum as possible.

57 of 68

Minimum spanning tree

A minimum spanning tree in a connected weighted graph is a spanning tree that has the smallest possible sum of weights of its edges.

Prim’s algorithm
Kruskal’s Algorithm

58 of 68

PRIM’S ALGORITHM

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

59 of 68

Example: Use Prims algorithm to find a minimal spanning tree for the graph below. Indicate the order in which edges are added to form the tree.�

Minimal spanning tree (MST)

60 of 68

Example: Use Prims algorithm to find a minimal spanning tree for the graph below. Indicate the order in which edges are added to form the tree.�

Order of adding the edges:

{a , b}, {b , c}, {c , d}, {d , e}, {e , f}, {f , g}

MST COST = 23

Minimal spanning tree (MST)

61 of 68

KRUSKAL’S ALGORITHM

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

62 of 68

Minimal spanning tree (MST)

Example: Use Kruskal’s algorithm to find a minimal spanning tree for the graph below. Indicate the order in which edges are added to form the tree.

63 of 68

Minimal spanning tree (MST)

Example: Use Kruskal’s algorithm to find a minimal spanning tree for the graph below. Indicate the order in which edges are added to form the tree.

MST COST = 23

64 of 68

11.4 Spanning Trees �Depth-First Search | Breadth-First Search | Backtracking Applications | Depth-First Search in Directed Graphs

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

65 of 68

11.4 Spanning Trees �Depth-First Search | Breadth-First Search | Backtracking Applications | Depth-First Search in Directed Graphs

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

66 of 68

11.4 Spanning Trees �Depth-First Search | Breadth-First Search | Backtracking Applications | Depth-First Search in Directed Graphs

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

67 of 68

11.4 Spanning Trees �Depth-First Search | Breadth-First Search | Backtracking Applications | Depth-First Search in Directed Graphs

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/

68 of 68

11.4 Spanning Trees �Depth-First Search | Breadth-First Search | Backtracking Application| Depth-First Search in Directed Graphs

FREE: For Complete Playlist: https://www.youtube.com/c/FahadHussaintutorial/playlists

For Code, Slide and Books: https://fahadhussaincs.blogspot.com/