Lesson7.Data Dtructures and Algorithm- Trees

About Lesson 7

1. COMP009
Data Structures &
Algorithms
Dr. Marygin E. Sarmiento
Professor

2. Lesson7
Tree Concept
Complete Binary
Tree
Traversing Trees

3. Learning Outcomes:
Discuss the Tree concept
Demonstrate Complete
Binary Tree
Identify the different
Traversing Trees

4. Tree
Tree is a non-empty
collection of vertices and
edges that satisfies certain
requirements.
Tree represents the nodes
connected by edges. We will
discuss binary tree or binary
search tree specifically.

6. Important Terms
Following are the important terms
to be remembered with respect
to tree.
Vertex – It is a simple object (also
referred to as a node) that can
have a name and can carry other
associated information.
Edge – it is a connection between
two vertices

7. Path − Path refers to the sequence of
nodes along the edges of a tree. It is also
a list of distinct vertices in which
successive vertices are connected by
edges in the tree
Root – It is the defining property of a
tree is that there is exactly one path
between the root and each of the other
nodes in the tree. The node at the top of
the tree is called root. There is only one
root per tree and one path from the root
node to any node.

8. Parent – It refers to any node except
the root node has one edge upward to
a node called parent.
Child − The node below a given node
connected by its edge downward is
called its child node.
Leaf/Leaves/Terminal Nodes − The
node which does not have any child
node is called the leaf node.

9. NonTerminal Nodes. These are
nodes that has at least one child.
Internal Nodes – Nonterminal
nodes.
External Nodes – Terminal nodes.
Subtree − Subtree represents the
descendants of a node. These are
nodes below the root.
Forest – It is a set of trees.

10. Level of Nodes – it is the
number of nodes in the path
from the node to the root(not
including itself).
Height – It is the maximum
level among all nodes in the
trees.
Path Length – It is the sum of
the levels of all the nodes in
the tree.

11. Complete Binary Tree
Binary Tree is a special data structure
used for data storage purposes. A
binary tree has a special condition
that each node can have a maximum
of two children. A binary tree has the
benefits of both an ordered array and
a linked list as search is as quick as in
a sorted array and insertion or
deletion operation are as fast as in
linked list.

13. ROOT = U
PATH = UMOC, UMP, UET, UERS= 4
VERTICES = C,O,M,P,U,T,E,R,S = 9
TERMINAL NODES =C,P,T,S=4
NONTERMINAL NODES = U,M,E,O,R
=5
EDGES = UM, MO, OC, MP, UE, ET, ER,
RS=8
LEVEL OF NODES = ME, OPTR, CS =
3
HEIGHT = 4
PATH LENGTH = 8

14. Lesson7.Activities
Instructions:
Create a complete binary and answer
the different parts of the tree based on the
following given :
1.DATA_STRUCTURE_AND_ALGORIT
HMS
2.COMMUNICATION_TECHNOLOGY
3.COMPUTER_SCIENCE
4.INFORMATION_TECHNOLOGY
5.POLYTECHNIC_UNIVERSITY

15. Traversing Trees
Tree traversal refers to the
process of visiting each individual
node exactly once. For our traversal,
we will focus on binary trees, which
are trees that have a max of two
children. 
It is how to systematically visit
every node in the tree

16. Types of Traversal Trees
1.Pre-order – Visit the root, visit the left
subtree, then visit the right subtree. R
L R
2.In Order – visit the left subtree, then
visit the root, then visit the right
subtree. L R R
3.Post Order – visit the left subtree, then
visit the right subtree and then visit
the root. LR R
4.Level Order – visit the root, all the way
from left to right node in every level of
the tree.

18. Pre order = Visit the root, visit the left subtree, then visit the
right subtree.
Level 1 = 1 2 6
Level 2 = 1 2 4 5 6 8 9
Level 3 = 1 2 4 7 5 6 8 9 3
 
In Order – visit the left subtree, then visit the root, then visit
the right subtree. L R R
Level 1 = 2 1 6
4 5 8 9
Level 2 = 4 2 5 1 8 6 9
7 3
 Level 3 = 7 4 2 5 1 8 6 9 3
 

19. Post Order – visit the left subtree, then visit the right subtree and
then visit the root. LR R
 
Level 1 - 2 6 1
4 5 8 9
Level 2 = 4 5 2 8 9 6 1
7 3
 Level 3 = 7 4 5 2 8 3 9 6 1
  
Level Order – visit the root, all the way from left to right node in
every level of the tree.
Level 1 = 1 2 6
Level 2 = 1 2 6 4 5 8 9
Level 3 = 1 2 6 4 5 8 9 7 3

24. Hands On Activity
Modify the above
program that will display the
level of Traversing Trees,
how it visits every node in
the tree.