Trees - Part 1 Notes | EduRev

: Trees - Part 1 Notes | EduRev

 Page 1


1
Trees : Part 1
Section 4.1
(1) Theory and Terminology
(2) Preorder, Postorder and
      Levelorder Traversals
Theory and Terminology
?Definition:  A tree is a connected graph
with no cycles
?Consequences:
?Between any two vertices, there is exactly one
unique path
A Tree?
1
2 3 4
5 6 8 7
9 10 12 11
A Tree?
1
2 3 4
5 6 8 7
9 10 12 11
Theory and Terminology
?Definition:  A rooted tree is a graph G
such that:
?G is connected
?G has no cycles
?G has exactly one vertex called the root of the
tree
Theory and Terminology
?Consequences
?The depth of a vertex  v  is the length of the
unique path from root to  v
?G can be arranged so that the root is at the top,
its neighboring vertices are vertices of depth 1,
and so on…
?The set of all vertices of depth k is called level k
of the tree
Page 2


1
Trees : Part 1
Section 4.1
(1) Theory and Terminology
(2) Preorder, Postorder and
      Levelorder Traversals
Theory and Terminology
?Definition:  A tree is a connected graph
with no cycles
?Consequences:
?Between any two vertices, there is exactly one
unique path
A Tree?
1
2 3 4
5 6 8 7
9 10 12 11
A Tree?
1
2 3 4
5 6 8 7
9 10 12 11
Theory and Terminology
?Definition:  A rooted tree is a graph G
such that:
?G is connected
?G has no cycles
?G has exactly one vertex called the root of the
tree
Theory and Terminology
?Consequences
?The depth of a vertex  v  is the length of the
unique path from root to  v
?G can be arranged so that the root is at the top,
its neighboring vertices are vertices of depth 1,
and so on…
?The set of all vertices of depth k is called level k
of the tree
2
A Rooted Tree
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
height = 2
height = 3
height = 0
height = 1
Rooted Tree: Recursive definition
? A graph with N  nodes and  N - 1  edges
? Graph has
?one root  r
?Zero or more non-empty sub-trees, each of whose root
is connected to  r  by an edge.
?Every node except the root has one parent
Theory and Terminology
? Definition:  A descending path in a rooted tree is
a path, whose edges go from a vertex to a
deeper vertex
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
3
8
12
Theory and Terminology
? Consequences:
?A unique path from the root to any vertex is a descending
path
?The length of this path is the depth of the vertex
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
1
3
8
11
Theory and Terminology
?Definition:  If there is a descending path
from v
1
  to  v
2
,  v
1
  is an ancestor of  v
2
,
and  v
2
  is a descendant of  v
1
.
Theory and Terminology
?Suppose v  is a vertex of depth  k:
?Any vertex that is adjacent to v  must have
depth k - 1  or  k + 1.
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
3
1
7 8
Page 3


1
Trees : Part 1
Section 4.1
(1) Theory and Terminology
(2) Preorder, Postorder and
      Levelorder Traversals
Theory and Terminology
?Definition:  A tree is a connected graph
with no cycles
?Consequences:
?Between any two vertices, there is exactly one
unique path
A Tree?
1
2 3 4
5 6 8 7
9 10 12 11
A Tree?
1
2 3 4
5 6 8 7
9 10 12 11
Theory and Terminology
?Definition:  A rooted tree is a graph G
such that:
?G is connected
?G has no cycles
?G has exactly one vertex called the root of the
tree
Theory and Terminology
?Consequences
?The depth of a vertex  v  is the length of the
unique path from root to  v
?G can be arranged so that the root is at the top,
its neighboring vertices are vertices of depth 1,
and so on…
?The set of all vertices of depth k is called level k
of the tree
2
A Rooted Tree
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
height = 2
height = 3
height = 0
height = 1
Rooted Tree: Recursive definition
? A graph with N  nodes and  N - 1  edges
? Graph has
?one root  r
?Zero or more non-empty sub-trees, each of whose root
is connected to  r  by an edge.
?Every node except the root has one parent
Theory and Terminology
? Definition:  A descending path in a rooted tree is
a path, whose edges go from a vertex to a
deeper vertex
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
3
8
12
Theory and Terminology
? Consequences:
?A unique path from the root to any vertex is a descending
path
?The length of this path is the depth of the vertex
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
1
3
8
11
Theory and Terminology
?Definition:  If there is a descending path
from v
1
  to  v
2
,  v
1
  is an ancestor of  v
2
,
and  v
2
  is a descendant of  v
1
.
Theory and Terminology
?Suppose v  is a vertex of depth  k:
?Any vertex that is adjacent to v  must have
depth k - 1  or  k + 1.
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
3
1
7 8
3
Theory and Terminology
?Suppose v  is a vertex of depth k:
?Vertices adjacent to  v  of depth k + 1  are
called children of  v.
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
3
7 8
Theory and Terminology
? Suppose v  is a vertex of depth  k:
?If  k > 0, there is exactly one vertex of depth  k – 1  that
is adjacent to  v  in the graph.
?This vertex is called the parent of  v.
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
3
1
Theory and Terminology
?Definitions
?A vertex with no children is called a leaf
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
Theory and Terminology
? Definitions
?Depth of a vertex  v  is its distance from the root.
?Height of a vertex v is the distance of the longest path from
v to one of its descendant leaves.
?The height of a tree is the maximum depth of its vertices
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
height
Theory and Terminology
? Definitions
?The root is the only vertex of depth 0.  The root has no
parent.
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
1
Example of rooted tree
? Which are the parent nodes?
? Which are the child nodes?
? Which are the leaves?
? What is the height and depth of the tree?
? What is the height and depth of node E? Node F?
Page 4


1
Trees : Part 1
Section 4.1
(1) Theory and Terminology
(2) Preorder, Postorder and
      Levelorder Traversals
Theory and Terminology
?Definition:  A tree is a connected graph
with no cycles
?Consequences:
?Between any two vertices, there is exactly one
unique path
A Tree?
1
2 3 4
5 6 8 7
9 10 12 11
A Tree?
1
2 3 4
5 6 8 7
9 10 12 11
Theory and Terminology
?Definition:  A rooted tree is a graph G
such that:
?G is connected
?G has no cycles
?G has exactly one vertex called the root of the
tree
Theory and Terminology
?Consequences
?The depth of a vertex  v  is the length of the
unique path from root to  v
?G can be arranged so that the root is at the top,
its neighboring vertices are vertices of depth 1,
and so on…
?The set of all vertices of depth k is called level k
of the tree
2
A Rooted Tree
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
height = 2
height = 3
height = 0
height = 1
Rooted Tree: Recursive definition
? A graph with N  nodes and  N - 1  edges
? Graph has
?one root  r
?Zero or more non-empty sub-trees, each of whose root
is connected to  r  by an edge.
?Every node except the root has one parent
Theory and Terminology
? Definition:  A descending path in a rooted tree is
a path, whose edges go from a vertex to a
deeper vertex
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
3
8
12
Theory and Terminology
? Consequences:
?A unique path from the root to any vertex is a descending
path
?The length of this path is the depth of the vertex
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
1
3
8
11
Theory and Terminology
?Definition:  If there is a descending path
from v
1
  to  v
2
,  v
1
  is an ancestor of  v
2
,
and  v
2
  is a descendant of  v
1
.
Theory and Terminology
?Suppose v  is a vertex of depth  k:
?Any vertex that is adjacent to v  must have
depth k - 1  or  k + 1.
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
3
1
7 8
3
Theory and Terminology
?Suppose v  is a vertex of depth k:
?Vertices adjacent to  v  of depth k + 1  are
called children of  v.
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
3
7 8
Theory and Terminology
? Suppose v  is a vertex of depth  k:
?If  k > 0, there is exactly one vertex of depth  k – 1  that
is adjacent to  v  in the graph.
?This vertex is called the parent of  v.
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
3
1
Theory and Terminology
?Definitions
?A vertex with no children is called a leaf
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
Theory and Terminology
? Definitions
?Depth of a vertex  v  is its distance from the root.
?Height of a vertex v is the distance of the longest path from
v to one of its descendant leaves.
?The height of a tree is the maximum depth of its vertices
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
height
Theory and Terminology
? Definitions
?The root is the only vertex of depth 0.  The root has no
parent.
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
1
Example of rooted tree
? Which are the parent nodes?
? Which are the child nodes?
? Which are the leaves?
? What is the height and depth of the tree?
? What is the height and depth of node E? Node F?
4
Overview of Tree Implementation
? Each node points to
?Its first child
?Its next sibling
?Back to its parent (optional)
? What could be an alternate representation?
Tree Traversals
?Definition:  A traversal is the process for
“visiting” all of the vertices in a tree
?Often defined recursively
?Each kind corresponds to an iterator type
?Iterators are implemented non-recursively
Preorder Traversal
?Visit vertex, then visit child vertices
(recursive definition)
?Depth-first search
?Begin at root
?Visit vertex on arrival arrival
?Implementation may be recursive, stack-
based, or nested loop
Preorder Traversal
1
2 3 4
5 6 8 7
root
2
5 6
3
7 8
4
Preorder Traversal of
UNIX Directory Tree
Postorder Traversal
?Visit child vertices, then visit vertex
(recursive definition)
?Depth-first search
?Begin at root
?Visit vertex on departure departure
?Implementation may be recursive, stack-
based, or nested loop
Page 5


1
Trees : Part 1
Section 4.1
(1) Theory and Terminology
(2) Preorder, Postorder and
      Levelorder Traversals
Theory and Terminology
?Definition:  A tree is a connected graph
with no cycles
?Consequences:
?Between any two vertices, there is exactly one
unique path
A Tree?
1
2 3 4
5 6 8 7
9 10 12 11
A Tree?
1
2 3 4
5 6 8 7
9 10 12 11
Theory and Terminology
?Definition:  A rooted tree is a graph G
such that:
?G is connected
?G has no cycles
?G has exactly one vertex called the root of the
tree
Theory and Terminology
?Consequences
?The depth of a vertex  v  is the length of the
unique path from root to  v
?G can be arranged so that the root is at the top,
its neighboring vertices are vertices of depth 1,
and so on…
?The set of all vertices of depth k is called level k
of the tree
2
A Rooted Tree
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
height = 2
height = 3
height = 0
height = 1
Rooted Tree: Recursive definition
? A graph with N  nodes and  N - 1  edges
? Graph has
?one root  r
?Zero or more non-empty sub-trees, each of whose root
is connected to  r  by an edge.
?Every node except the root has one parent
Theory and Terminology
? Definition:  A descending path in a rooted tree is
a path, whose edges go from a vertex to a
deeper vertex
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
3
8
12
Theory and Terminology
? Consequences:
?A unique path from the root to any vertex is a descending
path
?The length of this path is the depth of the vertex
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
1
3
8
11
Theory and Terminology
?Definition:  If there is a descending path
from v
1
  to  v
2
,  v
1
  is an ancestor of  v
2
,
and  v
2
  is a descendant of  v
1
.
Theory and Terminology
?Suppose v  is a vertex of depth  k:
?Any vertex that is adjacent to v  must have
depth k - 1  or  k + 1.
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
3
1
7 8
3
Theory and Terminology
?Suppose v  is a vertex of depth k:
?Vertices adjacent to  v  of depth k + 1  are
called children of  v.
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
3
7 8
Theory and Terminology
? Suppose v  is a vertex of depth  k:
?If  k > 0, there is exactly one vertex of depth  k – 1  that
is adjacent to  v  in the graph.
?This vertex is called the parent of  v.
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
3
1
Theory and Terminology
?Definitions
?A vertex with no children is called a leaf
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
Theory and Terminology
? Definitions
?Depth of a vertex  v  is its distance from the root.
?Height of a vertex v is the distance of the longest path from
v to one of its descendant leaves.
?The height of a tree is the maximum depth of its vertices
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
height
Theory and Terminology
? Definitions
?The root is the only vertex of depth 0.  The root has no
parent.
1
2 3 4
5 6 8 7
9 10 12 11
root
depth = 1
depth = 0
depth = 3
depth = 2
1
Example of rooted tree
? Which are the parent nodes?
? Which are the child nodes?
? Which are the leaves?
? What is the height and depth of the tree?
? What is the height and depth of node E? Node F?
4
Overview of Tree Implementation
? Each node points to
?Its first child
?Its next sibling
?Back to its parent (optional)
? What could be an alternate representation?
Tree Traversals
?Definition:  A traversal is the process for
“visiting” all of the vertices in a tree
?Often defined recursively
?Each kind corresponds to an iterator type
?Iterators are implemented non-recursively
Preorder Traversal
?Visit vertex, then visit child vertices
(recursive definition)
?Depth-first search
?Begin at root
?Visit vertex on arrival arrival
?Implementation may be recursive, stack-
based, or nested loop
Preorder Traversal
1
2 3 4
5 6 8 7
root
2
5 6
3
7 8
4
Preorder Traversal of
UNIX Directory Tree
Postorder Traversal
?Visit child vertices, then visit vertex
(recursive definition)
?Depth-first search
?Begin at root
?Visit vertex on departure departure
?Implementation may be recursive, stack-
based, or nested loop
5
Postorder Traversal
1 root
2 3 4
5 6 7 8
2
5 5 6 6
2 3
7 7 8 8
3 4 4
1
Postorder Traversal
Calculating Size of Directory
Levelorder Traversal
?Visit all vertices in level, starting with level
0 and increasing
?Breadth-first search
?Begin at root
?Visit vertex on departure
?Only practical implementation is queue-
based
Levelorder Traversal
1 root
2 3 4
5 6 7 8
2
5 5 6 6
2 3
7 7 8 8
3 4 4
1
Tree Traversals
?Preorder:  depth-first search (possibly
stack-based), visit on arrival
?Postorder:  depth-first search (possibly
stack-based), visit on departure
?Levelorder:  breadth-first search (queue-
based), visit on departure
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!