Republic of the Philippines
NORTHERN ILOILO POLYTECHNIC STATE COLLEGE
Lemery Campus, Lemery, Iloilo
CC 104: Data Structure and Algorithm REYLAN B.
VILI
NIPSCLC-BSIT INSTRUCTOR 3
First Semester AY 2020-21
Module 6, Lesson 6
Introduction to Binary Tree Page | 1
Introduction
In this module, you shall be introduced to the Binary Tree
Algorithm. This algorithm is a method by which students use in order to
understand the different traversal processes.
Learning Objectives:
1. To provide the knowledge Binary Tree Algorithm;
2. To develop the skill in Binary Tree Algorithm;
3. To teach how to create a representation showing the process of
Binary Tree Algorithm.
Learning Outputs: Upon completion of this Module, you shall be able to:
1. Describe the Binary Tree Algorithm;
2. Write a solution to a programming problem using Binary Tree
Algorithm;
3. Create a representation showing the process of Binary Tree
Algorithm.
Discussion
A. Introduction to Binary Trees.
A binary tree is a hierarchical data structure in which each node
has at most two children generally referred as left child and right child.
Each node contains three components:
1. Pointer to left subtree
2. Pointer to right subtree
3. Data element
The topmost node in the tree is called the root. An empty tree is represented
by NULL pointer.
CC 104: Data Structure and Algorithm REYLAN B.
VILI
NIPSCLC-BSIT INSTRUCTOR 3
First Semester AY 2020-21
1
Republic of the Philippines
NORTHERN ILOILO POLYTECHNIC STATE COLLEGE
Lemery Campus, Lemery, Iloilo
A representation of binary tree is shown:
Page | 2
Binary Tree: Common Terminologies
Root: Topmost node in a tree.
Parent: Every node (excluding a root) in a tree is connected by a
directed edge from exactly one other node. This node is called a
parent.
Child: A node directly connected to another node when moving away
from the root.
Leaf/External node: Node with no children.
Internal node: Node with atleast one children.
Depth of a node: Number of edges from root to the node.
Height of a node: Number of edges from the node to the deepest
leaf. Height of the tree is the height of the root.
CC 104: Data Structure and Algorithm REYLAN B.
VILI
NIPSCLC-BSIT INSTRUCTOR 3
First Semester AY 2020-21
2
Republic of the Philippines
NORTHERN ILOILO POLYTECHNIC STATE COLLEGE
Lemery Campus, Lemery, Iloilo
Page | 3
In the above binary tree we see that root node is A. The tree has 10 nodes
with 5 internal nodes, i.e, A,B,C,E,G and 5 external nodes, i.e, D,F,H,I,J. The
height of the tree is 3. B is the parent of D and E while D and E are children
of B.
Advantages of Trees
Trees are so useful and frequently used, because they have some very
serious advantages:
Trees reflect structural relationships in the data.
Trees are used to represent hierarchies.
Trees provide an efficient insertion and searching.
Trees are very flexible data, allowing to move subtrees around with
minimum effort.
Types of Binary Trees (Based on Structure)
Rooted binary tree: It has a root node and every node has atmost
two children.
Full binary tree: It is a tree in which every node in the tree has either
0 or 2 children.
CC 104: Data Structure and Algorithm REYLAN B.
VILI
NIPSCLC-BSIT INSTRUCTOR 3
First Semester AY 2020-21
3
Republic of the Philippines
NORTHERN ILOILO POLYTECHNIC STATE COLLEGE
Lemery Campus, Lemery, Iloilo
Page | 4
o The number of nodes, n, in a full binary tree is atleast n = 2h – 1,
and atmost n = 2h+1 – 1, where h is the height of the tree.
o The number of leaf nodes l, in a full binary tree is number, L of
internal nodes + 1, i.e, l = L+1.
Perfect binary tree: It is a binary tree in which all interior nodes have
two children and all leaves have the same depth or same level.
CC 104: Data Structure and Algorithm REYLAN B.
VILI
NIPSCLC-BSIT INSTRUCTOR 3
First Semester AY 2020-21
4
Republic of the Philippines
NORTHERN ILOILO POLYTECHNIC STATE COLLEGE
Lemery Campus, Lemery, Iloilo
o A perfect binary tree with l leaves has n = 2l-1 nodes.
o In perfect full binary tree, l = 2h and n = 2h+1 - 1 where, n is
number of nodes, h is height of tree and l is number of leaf nodes
Complete binary tree: It is a binary tree in which every level, except Page | 5
possibly the last, is completely filled, and all nodes are as far left as
possible.
o The number of internal nodes in a complete binary tree of n
nodes is floor (n/2).
Balanced binary tree: A binary tree is height balanced if it satisfies
the following constraints:
1. The left and right subtrees' heights differ by at most one, AND
2. The left subtree is balanced, AND
3. The right subtree is balanced
CC 104: Data Structure and Algorithm REYLAN B.
VILI
NIPSCLC-BSIT INSTRUCTOR 3
First Semester AY 2020-21
5
Republic of the Philippines
NORTHERN ILOILO POLYTECHNIC STATE COLLEGE
Lemery Campus, Lemery, Iloilo
An empty tree is height balanced.
Page | 6
o The height of a balanced binary tree is O(Log n) where n is
number of nodes.
Degenarate tree: It is a tree is where each parent node has only one
child node. It behaves like a linked list.
CC 104: Data Structure and Algorithm REYLAN B.
VILI
NIPSCLC-BSIT INSTRUCTOR 3
First Semester AY 2020-21
6
Republic of the Philippines
NORTHERN ILOILO POLYTECHNIC STATE COLLEGE
Lemery Campus, Lemery, Iloilo
Summary
A rooted binary tree is a tree with a root node in which every node has Page | 7
at most two children. A full binary tree (sometimes called as proper binary
tree or 2-tree or strictly binary tree) is a tree in which every node other than
the leaves has two children.
This is also a method showing more types of algorithm which being used by
the computer in sorting files.
Assessment
1. Describe in not less than 4 sentences the difference of perfect binary tree,
complete, binary tree, balance binary tree, and degenerate tree.
(5 points for each correct answer)
2. Why IT students need to study Binary Tree algorithm? (5 points)
Reference
[Link]
graph_data_structure.htm
[Link]
-End of Module 6, Lesson 6
CC 104: Data Structure and Algorithm REYLAN B.
VILI
NIPSCLC-BSIT INSTRUCTOR 3
First Semester AY 2020-21
7