ICT 224

DATA STRUCTURES AND ALGORITHMS

(DSA)

Lecturer:
Matthew Cobbinah
0547900989
[email protected]

School Of Technology
Christ Apostolic University College
LECTURE SEVEN

TREES
Natural View of a Tree

leaves

branches
root
Computer Scientist’s View

root

leaves

branches
nodes
What is a Tree?
◼ A tree data structure is defined as a collection of objects
or entities known as nodes that are linked together to
represent or simulate hierarchy.
 A Tree is a hierarchical data structure represented as collection of
nodes (starting at a root node), where each node consist of a
value, together with a list of references to other nodes(the
“children”) .
 It can also be defined as a non-linear data structure in which data
elements have hierarchical relationship.
◼ A tree data structure is a non-linear data structure
because it does not store in a sequential manner.
◼ It is a hierarchical structure as elements in a Tree are
arranged in multiple levels.
What is a Tree?
◼ In the Tree data structure, the topmost node is known as
a root node.
◼ Each node contains some data, and data can be of any
type.
◼ Each node contains some data and the link or reference
of other nodes that can be called children.
◼ The tree is also known as a recursive data structure.
 because the distinguished node in a tree data structure is known
as a root node.
Why a tree?

◼ Faster than linear data structures

◼ More natural fit for some kinds of data
◼ The tree data structure provides quicker access to the
data which is non-linear.
◼ Availability of the various types of data structures and
the algorithms associated with them, the task
performance has become an easy and efficient way.
Tree Terminology
◼ Node: An entity in a tree data structure that contains a
key or a value and pointers to its child nodes.
◼ Root: The root node is the topmost node in the tree
hierarchy.
◼ Parent: If a node contains any sub-node, then that node
is said to be the parent of that sub-node.
◼ Children/child node: A child node is the descendant of
any node
◼ Descendant: The immediate successor of the given
node is known as a descendant of a node
◼ Siblings: The nodes that have the same parent are
known as siblings.
◼ Leaf nodes: The nodes which don’t have any child nodes
and are the bottom-most node in a tree. They are also
called the external nodes.
Tree Terminology
◼ Internal nodes: A node that has at least one child node
◼ Ancestor node: An ancestor of a node is any
predecessor node on a path from the root to that node.
 The root node doesn't have any ancestors.
◼ Forest: A collection of disjoint trees.
Properties of Tree data structure
Properties of Tree data structure
◼ Number of edges: If there are n nodes, then there would
be n-1 edges.
 Each arrow in the structure represents the link or path.
 Each node, except the root node, will have at least one incoming
link known as an edge.
 There would be one link for the parent-child relationship.
Properties of Tree data structure
◼ Height of a node: Number of edges/links from the node
to the deepest leaf.
◼ Depth of a node: Number of edges/links from the root to
the node.
◼ Height of a tree: Height of the root node.
◼ Degree of a node: Total number of branches to that
node.
Applications of trees
1. Storing naturally hierarchical data: Trees are used to
store the data in the hierarchical structure.
 For example, the file system. The file system stored on the disc
drive, the file and folder are in the form of the naturally hierarchical
data and stored in the form of trees.
2. Organize data: It is used to organize data for efficient
insertion, deletion and searching.
 For example, a binary tree has a logN time for searching an
element.
Applications of trees…
3. Trie: It is a special kind of tree that is used to store the
dictionary.
 It is a fast and efficient way for dynamic spell checking.
4. Heap: It is also a tree data structure implemented using
arrays.
 It is used to implement priority queues.
5. B-Tree and B+Tree: B-Tree and B+Tree are the tree
data structures used to implement indexing in databases.
6. Routing table: The tree data structure is also used to
store the data in routing tables in the routers.
Tree Traversals
◼ Any process for visiting the nodes in some order is called
a traversal.
◼ Any traversal that lists every node in the tree exactly
once is called an enumeration of the tree’s nodes.
◼ Three methods for traversal
 Preorder
 Postorder
 Inorder

15
Tree Traversals…
◼ Preorder traversal:
 Visit each node before visiting its children.
 Visit node, traverse left subtree, traverse right subtree
 So the node first before its children/descendants
◼ Root, then Children
 prefix
expression
 Application: print a structured document
Algorithm preOrder(v)
◼ Preorder Algorithm: visit(v)
1 for each child w of v
Become Rich
preorder (w)

2 5 9
1. Motivations 2. Methods 3. Success Stories

3 4 6 7 8
1.1 Enjoy 1.2 Help 2.1 Get a 2.2 Start a 2.3 Acquired
Life Poor Friends CS PhD Web Site by Google

16
Tree Traversals…
◼ Postorder traversal:
 Visit each node after visiting its children.
 Traverse left subtree, traverse right subtree, visit node
 So the children/descend first before the nodes
◼ Children, then Root
 postfix expression
 Application: compute space used by files in a
directory and its subdirectories Algorithm postOrder(v)
◼ Postorder Algorithm: for each child w of v
9 postOrder (w)
cs16/
visit(v)
8
3 7
todo.txt
homeworks/ programs/
1K

1 2 4 5 6
h1c.doc h1nc.doc DDR.java Stocks.java Robot.java
3K 2K 10K 25K 20K

17
Tree Traversals…
EXAMPLE 1:
◼ Preorder – CAUC, SoT, ICT, AIT, Education, B.ED IT, BASIC EDU.
◼ Postorder – ICT, AIT, SoT, B.ED IT, BASIC EDU., Education, CAUC

root
CAUC

Education
SoT

B.ED IT BASIC EDU.

ICT AIT
Tree Traversals…
EXAMPLE 2:
◼ Preorder – CAUC, LEVEL 200, SEM 1, PROGRAMMING, DSA, JAVA, SEM 2
◼ Postorder – DSA, JAVA, PROGRAMMING, SEM 1, SEM 2, LEVEL 200, CAUC

root
CAUC

LEVEL 200

SEM 1 SEM 2

PROGRAMMING

DSA JAVA
Tree Traversals…
◼ Inorder traversal:
 Visit the left subtree, then the node, then the right
subtree.
 Traverse left subtree, visit node, traverse right subtree
 So left children first, then the nodes, before the right
children
◼ Left child, Root, Right child
 infix expression

20
Tree Traversals…
◼ Inorder traversal:
 Example 1:
 Output: ICT, SoT, AIT, CAUC, B.ED IT, EDUCATION, BASIC ED.

root
CAUC

Education
SoT

B.ED IT BASIC EDU.

ICT AIT

21
Tree Traversals…
◼ Inorder traversal:
 Example 2:
 Output: CAUC, DSA, PROGRAMMING, JAVA, SEM 1, LEVEL 200, SEM 2

root
CAUC

LEVEL 200

SEM 1 SEM 2

PROGRAMMING

DSA JAVA

22
TRIAL
◼ Traverse the tree below in the following
order +
 Preorder
 Postorder A *
 Inorder

B /

C D

ICT 224– DATA STRUCTURES AND ALGORITHMS, By 23

Matthew Cobbinah
Traversal Implementation
/** @param rt The root of the subtree */
void preorder(BinNode rt)
{
if (rt == null) return; // Empty subtree
visit(rt);
preorder(rt.left());
preorder(rt.right());
}

24
Preorder Traversal (recursive version)
void preorder(tree_pointer ptr)
/* preorder tree traversal */
{ +**/ABCDE
if (ptr) {
printf(“%d”, ptr->data);
preorder(ptr->left_child);
predorder(ptr->right_child);
}
}

25
Postorder Traversal (recursive version)

void postorder(tree_pointer ptr)

/* postorder tree traversal */
{
AB/C*D*E+
if (ptr) {
postorder(ptr->left_child);
postdorder(ptr->right_child);
printf(“%d”, ptr->data);
}
}

26
Inorder Traversal (recursive version)
void inorder(tree_pointer ptr)
/* inorder tree traversal */
{
if (ptr) {
A/B*C*D+E
inorder(ptr->left_child);
printf(“%d”, ptr->data);
indorder(ptr->right_child);
}
}

27
Types of Tree data structure
1. General tree:
 In the general tree, a node can have either 0 or
maximum n number of nodes.
 There is no restriction imposed on the degree of the
node (the number of nodes that a node can contain).
 The topmost node in a general tree is known as a
root node.
 The children of the parent node are known as
subtrees
Types of Tree data structure
1. General tree:
Types of Tree data structure
2. Binary tree
 Binary name itself suggests two numbers, i.e., 0 and
1.
 Is a type of tree data structure where every parent
node has a maximum of two child nodes
 In a binary tree, each node in a tree can have utmost
two child nodes.
 Here, utmost means whether the node has 0 nodes, 1
node or 2 nodes.
Types of Tree data structure
2. Binary tree
A

B C

D E F G

H I
Maximum Number of Nodes in BT
The maximum number of nodes on depth i of a
binary tree is 2i, i>=0.
The maximum number of nodes in a binary tree of
height k is 2k+1-1, k>=0.

Prove by induction.
k

 2
i =0
i
= 2 k +1
−1
Types of Binary Tree
1. Full/ proper/ strict Binary tree
2. Complete Binary tree
3. Perfect Binary tree
4. Degenerate Binary tree
5. Balanced Binary tree
Types of Binary Tree
◼ Full/ proper/ strict Binary tree
 The full binary tree is also known as a strict binary tree.
 The tree can only be considered as the full binary tree
if each node contain either 0 or 2 children.
 The full binary tree can also be defined as the tree in
which each node must contain 2 children except the
leaf nodes
Types of Binary Tree
◼ Complete Binary Tree
 The complete binary tree is a tree in which all the
nodes are completely filled except the last level.
 In the last level, all the nodes must be as left as
possible.
 In a complete binary tree, the nodes should be added
from the left.
Types of Binary Tree
◼ Perfect Binary Tree
 A tree is a perfect binary tree if all the internal nodes
have 2 children, and all the leaf nodes are at the same
level.
Types of Binary Tree
◼ Degenerate Binary Tree
 The degenerate binary tree is a tree in which all the
internal nodes have only one child.
 It is known as a right-skewed tree when all the nodes
have a right child only.
 It is known as a left-skewed tree when all the nodes
have a left child only.
Types of Binary Tree
◼ Balanced Binary Tree
 The balanced binary tree is a tree in which both the left
and right trees differ by at most 1.
◼ For example, AVL and Red-Black trees
Types of Tree data structure
3. Binary Search tree
 These tree structures are non-linear and one node is connected
to a number of nodes.
 The node can be connected to at most two child nodes.
4. AVL Tree:
 The AVL trees are the types or variants of a binary tree.
 It consists of properties from both the binary as well as a binary
search tree.
 Invented by Adelson, Velsky, Lindas, these trees are self-
balancing which means the height of the left subtree and the right
subtree is balanced.
 This balance is measured in terms of a balancing factor
Types of Tree data structure
3. Red-Black Tree
 …..
4. Splay tree:
 …
5. Treap
 Treap data structure came from the Tree and Heap data
structure.
Q/A
T for Thanks
ICT 224– DATA STRUCTURES AND ALGORITHMS,
By Matthew Cobbinah 41