Data Structures and Algorithm Analysis

Tree Data Structure

Presented by: Dr. Sammer Zai

Assistant Professor
Department of Computer Systems, Mehran, UET.

1
 Fair Use Notice

The material used in this presentation i.e., pictures/graphs/text, etc.

is solely intended for educational/teaching purpose, offered free of
cost to the students for use under special circumstances of Online
Education due to COVID-19 Lockdown situation and may include
copyrighted material - the use of which may not have been
specifically authorized by Copyright Owners. It’s application
constitutes Fair Use of any such copyrighted material as provided in
globally accepted law of many countries. The contents of
presentations are intended only for the attendees of the class being
conducted by the presenter.
 Contents

• What is a Tree?
• Tree Terminologies
• Unlabeled Binary Tree
• Labeled Binary Tree
• Binary Tree
• Types of Binary Tree
• Binary Tree Traversal

3
Tree

4
What is a Tree Data Structure?
• Tree is a non-linear data structure which organizes data in a
hierarchical structure and this is a recursive definition.
OR
• A tree is a connected graph without any circuits.
OR
• If in a graph, there is one and only one path between every pair of
vertices, then graph is called as a tree.

5
Tree - Example

6
Tree Terminology

7
Root
• The first node from where the
tree originates is called as a root
node.
• In any tree, there must be only
one root node.
• We can never have multiple
root nodes in a tree data
structure.

8
Edge
• The connecting link between any
two nodes is called as an edge.
• In a tree with n number of nodes,
there are exactly (n-1) number of
edges.

9
Parent
• The node which has a branch
from it to any other node is
called as a parent node.
• In other words, the node which
has one or more children is
called as a parent node.
• In a tree, a parent node can have
any number of child nodes.

10
Parent (Continue…)
• Here,
• Node A is the parent of nodes B and C
• Node B is the parent of nodes D, E and F
• Node C is the parent of nodes G and H
• Node E is the parent of nodes I and J
• Node G is the parent of node K

11
Child
• The node which is a
descendant of some node is
called as a child node.
• All the nodes except root node
are child nodes.

12
Siblings
• Nodes which belong to the same
parent are called as siblings.
• In other words, nodes with the
same parent are sibling nodes.
• Here,
• Nodes B and C are siblings
• Nodes D, E and F are siblings
• Nodes G and H are siblings
• Nodes I and J are siblings
•

13
Degree
• Degree of a node is the total number of children of that
node.
• Degree of a tree is the highest degree of a node among all
the nodes in the tree.
• Here,
• Degree of node A = 2
• Degree of node B = 3
• Degree of node C = 2
• Degree of node D = 0
• Degree of node E = 2
• Degree of node F = 0
• Degree of node G = 1
• Degree of node H = 0
• Degree of node I = 0
• Degree of node J = 0
• Degree of node K = 0

14
 Internal Node
• The node which has at
least one child is called as
an internal node.
• Internal nodes are also
called as non-terminal
nodes.
• Every non-leaf node is an
internal node.

15
Leaf Node
• The node which does
not have any child is
called as a leaf node.
• Leaf nodes are also
called as external
nodes or terminal
nodes.
• Here, nodes D, I, J, F, K
and H are leaf nodes

16
Level
• n a tree, each step
from top to bottom is
called as level of a
tree.
• The level count starts
with 0 and increments
by 1 at each level or
step.

17
Height
• Total number of edges that lies on the longest path from any
leaf node to a particular node is called as height of that node.
• Height of a tree is the height of root node.
• Height of all leaf nodes = 0

18
Height (Continue…)
• Here,
• Height of node A = 3
• Height of node B = 2
• Height of node C = 2
• Height of node D = 0
• Height of node E = 1
• Height of node F = 0
• Height of node G = 1
• Height of node H = 0
• Height of node I = 0
• Height of node J = 0
• Height of node K = 0

19
Depth
• Total number of edges from root node to a particular node is called
as depth of that node.
• Depth of a tree is the total number of edges from root node to a leaf
node in the longest path.
• Depth of the root node = 0
• The terms “level” and “depth” are used interchangeably.

20
Depth (Continue…)

Here,
•Depth of node A = 0
•Depth of node B = 1
•Depth of node C = 1
•Depth of node D = 2
•Depth of node E = 2
•Depth of node F = 2
•Depth of node G = 2
•Depth of node H = 2
•Depth of node I = 3
•Depth of node J = 3
•Depth of node K = 3

21
SubTree
• In a tree, each child from a node forms a subtree recursively.
• Every child node forms a subtree on its parent node.

22
Forest
• A forest is a set of disjoint trees.

23
Binary Tree and Its
Types

24
Binary Tree
• Binary Tree is a special tree data structure in which each n ode can
have at most 2 children.
• Each node has either 0 child or 1 child or 2 children.

25
Binary Tree - Example

26
Unlabeled Binary Tree
• A binary tree is unlabeled if its nodes are not assigned any label.

27
Example
• Consider we want to draw all the binary trees possible with 3
unlabeled nodes.
• Using the above formula, we have-
•
• Number of binary trees possible with 3 unlabeled nodes
• = 2 x 3C3 / (3 + 1)
• = 6C3 / 4
•=5

28
• Thus,
• With 3 unlabeled nodes, 5 unlabeled binary trees are possible.
• These unlabeled binary trees are as follows;

29
Labeled Binary Tree
• A binary tree is labeled if all its nodes are assigned a label.

30
Example of Labeled Binary Tree
• Consider we want to draw all the binary trees possible with 3 labeled
nodes.
• Using the above formula, we have-
•
• Number of binary trees possible with 3 labeled nodes
• = { 2 x 3C3 / (3 + 1) } x 3!
• = { 6C3 / 4 } x 6
• =5x6
• = 30
•
31
Example of Labeled Binary Tree
• Thus,
• With 3 labeled nodes, 30 labeled
binary trees are possible.
• Each unlabeled structure gives rise
to 3! = 6 different labeled
structures.
• Similarly,
• Every other unlabeled structure
gives rise to 6 different labeled
structures.
• Thus, in total 30 different labeled
binary trees are possible.

32
Types of Binary Tree

33
Types of Binary Tree
1. Rooted Binary Tree
2. Full / Strictly Binary Tree
3. Complete / Perfect Binary Tree
4. Almost Complete Binary Tree
5. Skewed Binary Tree

34
1- Rooted Binary Tree
• A rooted binary tree is a binary tree that satisfies the following 2
properties-
• It has a root node.
• Each node has at most 2 children.

35
2- Full / Strictly Binary Tree
• A binary tree in which every node has either 0 or 2 children is called
as a Full binary tree.
• Full binary tree is also called as Strictly binary tree.

36
2- Full / Strictly Binary Tree
Here,
•First binary tree is not a full binary tree.
•This is because node C has only 1 child.

37
3- Complete Binary Tree
• A complete binary tree is a binary tree that satisfies the following 2
properties-
• Every internal node has exactly 2 children.
• All the leaf nodes are at the same level.
•
• Complete binary tree is also called as Perfect binary tree.

38
3- Complete Binary Tree
Here,
•First binary tree is not a complete binary tree.
•This is because all the leaf nodes are not at the same level.

39
4- Almost Complete Binary Tree
• An almost complete binary tree is a binary tree that satisfies the
following 2 properties-
• All the levels are completely filled except possibly the last level.
• The last level must be strictly filled from left to right.
•

40
4- Almost Complete Binary Tree
• Here,
• First binary tree is not an almost complete binary tree.
• This is because the last level is not filled from left to right.

41
5- Skewed Binary Tree
• A skewed binary tree is a binary tree that satisfies the following 2
properties-
• All the nodes except one node has one and only one child.
• The remaining node has no child.
• OR
• A skewed binary tree is a binary tree of n nodes such that its depth is
(n-1).

42
5- Skewed Binary Tree

43