Discrete Mathematics and

Its Applications
Kenneth H. Rosen
Chapter 9
Trees

1
 Tree

Definition 1. A tree is a connected

undirected graph with no simple circuits.

Theorem 1. An undirected graph is a tree if

and only if there is a unique simple path
between any two of its vertices.

2
 Which graphs are trees?
a) b)

c)

3
 Tournament Trees
A common form of tree used in everyday
life is the tournament tree, used to
describe the outcome of a series of
games, such as a tennis tournament.
Alice
Antoni Alice
a Alice
Abigail
Anita Alic
Abigail Agnes e
Amy Angel
Agnes Angela a
Angela
Audrey
 A Family Tree

Much of the tree terminology derives

from family trees.

Gae
a
Ocea
Cronu Phoeb
n
s e
Zeu Poseido Demet Plut Let Iapetu
s n er o o s
Apoll Atla Promethe
Persepho
o s us
ne
 Rooted Trees

Once a vertex of a tree has been designated

as the root of the tree, it is possible to
assign direction to each of the edges.

6
 Rooted Trees

g
a
e f e c
b
b
d
a d

c g
f
7
 Parent

● The parent of a non-root vertex v is the

unique vertex u with a directed edge
from u to v.

8
 What is the parent of Ed?

Lou

Hal Max

Ed Ken Sue

Joe Ted
9
 Leaf

● A vertex is called a leaf if it has no

children.

10
 How many leaves?

Lou

Hal Max

Ed Ken Sue

Joe Ted
11
 Ancestors

● The ancestors of a non-root vertex are

all the vertices in the path from root to
this vertex.

12
How many ancestors of Ken?

Lou

Hal Max

Ed Ken Sue

Joe Ted
13
 Descendants

● The descendants of vertex v are all the

vertices that have v as an ancestor.

14
How many descendants of Hal?

Lou

Hal Max

Ed Ken Sue

Joe Ted
15
 Internal Vertex

A vertex that has children is called an

internal vertex.

The subtree at vertex v is the subgraph of

the tree consisting of vertex v and its
descendants and all edges incident to
those descendants.

16
 root node
a
internal vertex parent of g
b c

d e f g

leaf
siblings
h i

17
 a

b c

d e f g

h i ancestors of h and i

18
 a

b c

d e f g

subtree with b as its

h i root
subtree with c as its
root
19
 Jake’s Pizza Shop Tree

Owner Jake

Manager Brad Chef

Carol

Waitress Waiter Cook

Helper
Joyce Chris Max
Len 20
 A Tree Has a Root
TREE
Owner Jake
ROOT

Manager Brad Chef Carol

Waitress Waiter Cook Helper

Joyce Chris Max Len

21
 Leaf nodes have no children

Owner Jake

Manager Brad Chef Carol

Waitress Waiter Cook Helper

Joyce Chris Max Len

LEAF NODES
22
 m-ary trees

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.

23
24
 Level of tree

● The level of a vertex in a rooted tree is

the length of the unique path from the
root to this vertex.
● The level of the root is defined to be
zero.
● The height of the rooted tree is the
maximum of the levels of vertices.

25
 Properties of Trees

The level of a vertex v in a rooted tree is

the length of the unique path from the root
to this vertex.

level 2

level 3

26
 Properties of Trees

The height of a rooted tree is the maximum

of the levels of vertices.

27
 Properties of Trees

A rooted m-ary tree of height h is called

balanced if all leaves are at levels h or h-1.

28
 A Tree Has Levels

LEVEL 0 Owner Jake

Manager Brad Chef Carol

Waitress Waiter Cook Helper

Joyce Chris Max Len

29
 Level One

Owner Jake

LEVEL 1 Manager Brad Chef Carol

Waitress Waiter Cook Helper

Joyce Chris Max Len

30
 Level Two

Owner Jake

Manager Brad Chef Carol

LEVEL 2

Waitress Waiter Cook Helper

Joyce Chris Max Len

31
 Sibling nodes have same parent

Owner Jake

SIBLINGS
Manager Brad Chef
Carol

Waitress Waiter Cook

Helper
Joyce Chris Max
Len 32
 Sibling nodes have same parent

Owner Jake

Manager Brad Chef Carol

Waitress Waiter Cook Helper

Joyce Chris Max Len

SIBLING
S 33
 A Subtree
ROOT
Owner Jake

Manager Brad Chef Carol

Waitress Waiter Cook Helper

Joyce Chris Max Len

LEFT SUBTREE OF 34
ROOT
 Another Subtree
ROOT
Owner Jake

Manager Brad Chef Carol

Waitress Waiter Cook Helper

Joyce Chris Max Len

RIGHT SUBTREE OF ROOT

35
 Binary Tree

Definition 2’. A rooted tree is called a

binary tree if every internal vertex has
no more than 2 children.

The tree is called a full binary tree if

every internal vertex has exactly 2
children.

36
 Ordered Rooted Tree

An ordered rooted tree is a rooted tree

where the children of each internal vertex
are ordered. Ordered trees are drawn so
that the children of each internal vertex
are shown in order from left to right.

37
 Tree Properties
Theorem 2. A tree with N vertices has N-1
edges.

38
 Properties of Trees

A tree with n vertices has n-1 edges.

39
 Properties of Trees

A full m-ary tree with i internal vertices

contains n = mi+1 vertices.

40
 Properties of Trees

A full m-ary tree with

(i) n vertices has i = (n-1)/m internal
vertices and l = [(m-1)n+1]/m leaves.
(ii) i internal vertices has n = mi + 1
vertices and l = (m-1)i + 1 leaves.
(iii) l leaves has n = (ml - 1)/(m-1) vertices
and i = (l-1)/(m-1) internal vertices.
41
 An Ordered Binary Tree

Lou

Hal Max

Ed Ken Sue

Joe Ted
42
 Balanced

● A rooted binary tree of height H is

called balanced if all its leaves are at
levels H or H-1.

43
Is this binary tree balanced?

Lou

Hal Max

Ed Ken Sue

Joe Ted
44
 Traversal Algorithms
● A traversal algorithm is a procedure for
systematically visiting every vertex of
an ordered binary tree.
● Tree traversals are defined recursively.
● Three traversals are named:
preorder,
inorder,
postorder.
45
PREORDER Traversal Algorithm
Let T be an ordered binary tree with root r.

If T has only r, then r is the preorder traversal.

Otherwise, suppose T1, T2 are the left and

right subtrees at r. The preorder traversal
begins by visiting r. Then traverses T1 in
preorder, then traverses T2 in preorder.
46
Preorder Traversal: J E A H T M Y
Visit
first.
ROOT

‘J
’
‘E’ ‘T’

‘A’ ‘H’ ‘M’ ‘Y’

Z
X

Visit left subtree second Visit right subtree

last 47
 INORDER Traversal Algorithm
Let T be an ordered binary tree with root r.

If T has only r, then r is the inorder traversal.

Otherwise, suppose T1, T2 are the left and
right subtrees at r. The inorder traversal
begins by traversing T1 in inorder. Then
visits r, then traverses T2 in inorder.

48
 Inorder Traversal: A E H J M T Y
Visit second

ROOT
‘J
’
‘E’ ‘T’

‘A’ ‘H’ ‘M’ ‘Y’

Visit left subtree Visit right subtree

first last 49
POSTORDER Traversal Algorithm
Let T be an ordered binary tree with root r.

If T has only r, then r is the postorder traversal.

Otherwise, suppose T1, T2 are the left and right
subtrees at r. The postorder traversal begins
by traversing T1 in postorder. Then traverses
T2 in postorder, then ends by visiting r.

50
Postorder Traversal: A H E M Y T J
Visit last

ROOT
‘J
’
‘E’ ‘T’

‘A’ ‘H’ ‘M’ ‘Y’

Visit left subtree Visit right subtree second

first 51
 A Binary Expression Tree

ROO
T

‘-’
‘8
’ ‘5’
INORDER TRAVERSAL: 8 - 5 has value 3

PREORDER TRAVERSAL: - 8 5

POSTORDER TRAVERSAL: 8 5 -
52
 A Binary Expression Tree is . . .
A special kind of binary tree in which:
1. Each leaf node contains a single operand,
2. Each nonleaf node contains a single binary
operator, and
3. The left and right subtrees of an operator
node represent subexpressions that must be
evaluated before applying the operator at
the root of the subtree.

53
 A Binary Expression Tree

‘*’

‘3
‘+’ ’
‘4 ‘2
’ ’
What value does it
have?

( 4 + 2 ) * 3 = 18 54
 A Binary Expression Tree

‘*’

‘3
‘+’ ’
‘4 ‘2
’ ’
What infix, prefix, postfix expressions does it
represent?

55
 A Binary Expression Tree

‘*’

‘3
‘+’ ’
‘4 ‘2
’ ’
Infix: ((4+2)*3)
Prefix: * + 4 2 3 evaluate from
right
Postfix: 4 2 + 3 * evaluate from left 56
Levels Indicate Precedence
When a binary expression tree is used to
represent an expression, the levels of the
nodes in the tree indicate their relative
precedence of evaluation.

Operations at higher levels of the tree are

evaluated later than those below them.
The operation at the root is always the
last operation performed.

57
 Evaluate
this binary expression tree
‘*’

‘-’ ‘/’

‘8 ‘5 ‘+’ ‘3
’ ’ ’
‘4 ‘2
’ ’
What infix, prefix, postfix expressions does it
represent? 58
 A binary expression tree
‘*’

‘-’ ‘/’

‘8 ‘5 ‘+’ ‘3
’ ’ ’
‘4 ‘2
’ ’
Infix: ((8-5)*((4+2)/3))
Prefix: *-85 /+423
Postfix: 8 5 - 4 2 + 3 / * has operators in order
used 59
 A binary expression tree
‘*’

‘-’ ‘/’

‘8’ ‘5’ ‘+’ ‘3’

‘4’ ‘2’

Infix: ((8-5)*((4+2)/3))
Prefix: *-85 /+423 evaluate from
right
Postfix: 85- 42+3/* evaluate from left60
Inorder Traversal: (A + H) / (M - Y)
Print
second
ROOT

‘/’

‘+’ ‘-’

‘A’ ‘H’ ‘M’ ‘Y’

Print left subtree Print right subtree

first last 61
 Preorder Traversal: / + A H - M Y
Print
first
ROOT

‘/’

‘+’ ‘-’

‘A’ ‘H’ ‘M’ ‘Y’

Print left subtree Print right subtree

second last 62
Postorder Traversal: A H + M Y - /
Print
last
ROOT

‘/’

‘+’ ‘-’

‘A’ ‘H’ ‘M’ ‘Y’

Print left subtree Print right subtree

first second 63
ACKNOWLEDGMENT:

This project was supported in part by

the National Science Foundation
under grant DUE-ATE 9950056.

64