S.Y.B.Sc.
(Computer Science)
Sem- IV
Subject: Data Structures and Algorithms – II
Chapter1 : Tree
By,
Mrs. Reshma Masurekar
Dr. D. Y. Patil ACS College,
Pimpri, Pune 18.
Chapter 1:Tree
• Concept and Terminologies
• Types of Binary trees - Binary tree, skewed tree, strictly binary
tree, full binary tree, complete binary tree, expression tree,
binary search tree, Heap
• Representation – Static and Dynamic
• Implementation and Operations on Binary Search Tree -
Create, Insert, Delete, Search, Tree traversals– preorder,
inorder, postorder ( recursive implementation), Level-order
traversal using queue, Counting leaf, non-leaf and total
nodes, Copy, Mirror.
• Applications of trees
Heap sort, implementation
Introduction to Greedy strategy, Huffman encoding
(implementation using priority queue)
Definition
• A tree is a non-linear data structure made up of nodes or
vertices and edges which is organized in hierarchical structure
(without having any cycle)
• In tree data structure, every individual element is called
as Node. Node in a tree data structure stores the actual data
of that particular element and link to next element in
hierarchical structure.
• collection of nodes that are connected by edges and has a
hierarchical relationship between the nodes.
• In a tree data structure, if we have N number of nodes then
we can have a maximum of N-1 number of links.
• The tree with no nodes is called the null or empty tree.
• A tree that is not empty consists of a root node and potentially
many levels of additional nodes that form a hierarchy.
Terminology
• Root node: The topmost node of a tree or the node which
does not have any parent node is called the root node. It
is the root node of the tree. A non-empty tree must contain
exactly one root node and exactly one path from the root
to all other nodes of the tree.
Ex.: {A} is the root node of the tree.
• Parent Node: The node which is a predecessor of a node
is called the parent node of that node. {B} is the parent
node of {D, E}.
• Child Node: The node which is the immediate successor
of a node is called the child node of that node.
Examples: {D, E} are the child nodes of {B}.
• Leaf Node or External Node: The nodes which do not
have any child nodes are called leaf nodes. {K, L, M, N,
O, P, G} are the leaf nodes of the tree.
• External Node: The node with no child node are called as
External node. Leaf nodes are also called as External Nodes.
• Internal node: A node with at least one child is called
Internal Node.
• Ancestor of a Node: Any predecessor nodes on the path
of the root to that node are called Ancestors of that
node. {A,B} are the ancestor nodes of the node {E}
• Descendant: Any successor node on the path from the
leaf node to that node. {E,I} are the descendants of the
node {B}.
• Sibling: Children of the same parent node are called
siblings. {D,E} are called siblings.
• Neighbour of a Node: Parent or child nodes of that node
are called neighbors of that node.
• Subtree: Any node of the tree along with its descendant.
Degree: the total number of children of a node is called
as degree of that Node. In simple words, the Degree of a
node is total number of children it has. The highest
degree of a node among all the nodes in a tree is called
as 'Degree of Tree‘.
Level of a node: The count of edges on the path from
the root node to that node.
In a tree each step from top to bottom is called as a
Level and the Level count starts with '0 ' and
incremented by one at each level (Step).
The root node is said to be at Level 0 and the children of
root node are at Level 1 and the children of the nodes
which are at Level 1 will be at Level 2 and so on...
Height of the node:
In a tree data structure, the total number of edges from leaf
node to a particular node in the longest path is called
as HEIGHT of that Node.
height of the tree: In a tree, height of the root node is said to
be height of the tree. In a tree, height of all leaf nodes is '0'.
Depth
In a tree data structure, the total number of egdes from root
node to a particular node is called as DEPTH of that Node.
In a tree, the total number of edges from root node to a leaf
node in the longest path is said to be Depth of the tree.
In simple words, the highest depth of any leaf node in a tree is
said to be depth of that tree. In a tree, depth of the root node
is '0'.
Path
In a tree data structure, the sequence of Nodes and Edges
from one node to another node is called as PATH between that
two Nodes.
Length of a Path is total number of nodes in that path.
Example the path A - B - E - J has length 4.
