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