Non - Linear data structure
➢ A Non- linear data structure is a data structure in which
data item is connected to several other data items
➢ Each data item is called a node.
➢ The data items in a non-linear data structure represent
hierarchical relationship.
➢ The data items are not arranged in a sequential structure
The different Non-linear data structures are:
➢ Trees
➢ Graphs
Non - Linear data structure
Advantages:
➢ Uses memory efficiently as contiguous memory is not
required for allocating data items
➢ The length of the data items is not necessary to be known
prior to allocation.
Disadvantages:
➢ Overhead of the link to the next data item
Tree Definition
➢ Tree data structure is a collection of data (Node) which is
organized in hierarchical structure recursively
➢ 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
➢ In a tree data structure, if we have N number of nodes then
we can have a maximum of N-1 number of links
1) NODE = 11
2) LINKS =11-1=10
Note
➢ Tree is a non-linear data structure.
➢ In a tree data structure, a node can have any number of
child nodes.
tree terminology
root
➢ The first node is called as Root Node.
➢ Every tree must have root node, there must be only one
root node.
➢ Root node doesn't have any parent.
A ROOT NODE
Edge
➢ In a tree data structure, the connecting link between any
two nodes is called as EDGE.
➢ In a tree with 'N' number of nodes there will be a maximum
of “ N-1 ” number of edges.
EDGE
Parent
➢ In a tree data structure, the Node which is predecessor
of any node is called as PARENT NODE.
➢ In simple words, the node which has branch from it to
any other node is called as parent node.
➢ Parent node can also be defined as "The node which
has child / children".
A Here ,
A, B, C , E, G are
PARENT NODE
B C
E G
Child
➢ In a tree data structure, the node which is descendant of
any node is called as Child Node
➢ In simple words, The node which has a link from its parent
node is called as child node.
➢ In a tree, any parent node can have any number of child
nodes.
➢ In a tree, all the nodes except root are child nodes.
A Here,
B and C – Children of A
B C D, E, F – Children of B
D E F G H G and H – Children of C
K – Child of G
I J K
I and J – Children of E
Siblings
➢ In a tree data structure, nodes which belong to same
parent are called as SIBLINGS
➢ In simple words, The nodes with same parent are called
as Sibling nodes.
Here,
B and C – SIBLINGS
D, E, F – SIBLINGS
G and H – SIBLINGS
I and J – SIBLINGS
Leaf Node
➢ The node which does not have a child is called as LEAF
Node.
➢ The leaf nodes are also called as External Nodes or
Terminal node.
Here,
D, F, I, J, K, H are
LEAF NODE
D F H
I J K
Internal Nodes
➢ In a tree data structure, The node which has at least one
child is called as an internal node
➢ In simple words, Internal node is a node with at least one
child
➢ Nodes other than leaf nodes are called as Internal Nodes.
➢ Root node is also called as internal node, if tree has more then
one node
➢ Internal nodes are also called as Non-terminal nodes.
Here,
A, B, C, E, G are
INTERNAL NODES
Degree
➢ In a tree data structure, the total number of children of a
node is called as DEGREE of that Node.
➢ In simple words, Degree of a node is the total number of
children it has
➢ The highest degree of a node among all the nodes in the
tree is called as Degree of a 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
Level
➢ In a tree data structure, 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...
➢ In simple words, 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).
LEVEL -- 00
LEVEL
LEVEL - 1
LEVEL - 2
LEVEL - 3
Height
➢ 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.
➢ In a tree, Height of the root node is said to be Height of
the tree.
➢ In a tree, Height of all leaf node is 0
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
Depth
➢ In a tree data structure, the 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 is said to be DEPTH of
that node
➢ Depth of the root node is 0
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
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.
Here,
▪ PATH between A and J is
A-B-E-J
▪ PATH between A and D is
A-B-D
Sub Tree
➢ In a tree data structure, each child node will form a
subtree recursively.
➢ Every child node will form a subtree on its parent node.
Here,
▪ B, D ,E, F, I, J form one
subtree
▪ C, G, H, K forms another
Subtree
▪ E, I, J forms another
subtree
BINARY TREE
➢ The simplest form of tree is a binary tree.
➢ A tree in which every node can have a maximum of two
children is called as binary tree
➢ A node can have just one but it can’t have more than two
B C
D E F G
BINARY TREE
➢ A binary tree consists of
❖ A node (called the root node)
❖ left and right sub-trees.
➢ Both the sub-trees are themselves binary trees.
➢ The importance of a binary tree is that it can create a data
structure that is “Yes/No” decision making process
BINARY TREE – Terminology
➢ Root Node:
❖ Node at the “top” of a tree - the one from which all
operations on the tree commence.
❖ The root node may not exist (a NULL tree with no
nodes in it) or have 0, 1 or 2 children in a binary tree.
➢ Leaf Node:
❖ Node at the “bottom” of a tree - farthest from the root.
❖ Leaf nodes have no children.
➢ Complete Tree: Tree in which each leaf is at the same
distance from the root i.e. all the nodes have maximum two
subtrees.
➢ Height: Number of nodes which must be traversed from the
root to reach a leaf of a tree.
GRAPHS
➢ A graph is an abstract data type that consists of a set of
objects that are connected to each other via links. These
objects are called vertices and the links are called edges.
➢ Vertex − Each node of the graph is represented as a vertex.
➢ Edge − Edge represents a path between two vertices or a
line between two vertices.
➢ Adjacency − Two node or vertices are adjacent if they are
connected to each other through an edge.
Types of GRAPHS
➢ There are two basic types of graph
❖ Directed Graph
❖ Undirected Graph
➢ Directed graph, as the name suggests, consists of edges
that possess a direction that goes either away from a vertex
or towards the vertex.
➢ Undirected graphs have edges that are not directed at all.
Neighbors and adjacency
➢ A vertex that is the end point of an edge is called a
neighbor of the vertex, that is its starting-point. The first
vertex is said to be adjacent to the second.
➢ The following diagram shows a Graph with 5 vertices and
7 edges. The edges between A and D and B and C are
pairs that make a bidirectional connection, represented
here by a double-headed arrow
