1.
Non-Linear Data Structures
Trees
Basics of Trees: Binary Trees , Binary Search Trees.
Tree Traversal Methods: In-order , Pre-order , Post-order , Level order.
Applications of Trees: Expression Trees , Decision Trees
Practical Problems.
Trees
Tree data structure is a hierarchical structure that is used to represent and organize data in
the form of parent child relationship. The following are some real world situations which are
naturally a tree.
Example:-
Folder structure in an operating system.
Tag structure in an HTML (root tag the as html tag) or XML document.
The topmost node of the tree is called the root, and the nodes below it are called the child
nodes. Each node can have multiple child nodes, and these child nodes can also have
their own child nodes, forming a recursive structure.
Basic Terminologies In Tree Data Structure:
[Link] Node: The node which is an immediate predecessor of a node is called the
parent node of that node. {B} is the parent node of {D, E}.
[Link] 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}.
[Link] Node: The topmost node of a tree or the node which does not have any parent
node is called the root node. {A} 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.
[Link] Node or External Node: The nodes which do not have any child nodes are called
leaf nodes. {I, J, K, F, G, H} are the leaf nodes of the tree.
[Link] of a Node: In a tree data structure, an ancestor of a node is any node that is
located on the path from the root to that node. This includes the node's parent,
grandparent, and all other nodes leading back to the root.
[Link]: Children of the same parent node are called siblings. {D,E} are called siblings.
[Link] of a node: The count of edges on the path from the root node to that node. The
root node has level 0.
[Link] node: A node with at least one child is called Internal Node.
[Link] of a Node: Parent or child nodes of that node are called neighbours of that
node.
[Link]: Any node of the tree along with its descendant.
Why Tree is considered a non-linear data structure?
The data in a tree are not stored in a sequential manner i.e., they are not stored linearly.
Instead, they are arranged on multiple levels or we can say it is a hierarchical structure. For
this reason, the tree is considered to be a non-linear data structure.
Representation of Tree Data Structure:
A tree consists of a root node, and zero or more subtrees T1, T2, … , Tk such that there is an
edge from the root node of the tree to the root node of each subtree. Subtree of a node X
consists of all the nodes which have node X as the ancestor node.
Importance for Tree Data Structure:
One reason to use trees might be because you want to store information that
naturally forms a hierarchy.
For example, the file system on a computer:
An HTML page is also tree where we have html tag as root, head and body its
children and these tags, then have their own children.
Types of Trees
The main types of trees in data structure are:
1. Binary Tree
A binary tree is a tree data structure where each node has at most two children. These two
children are usually referred to as the left child and right child. It is widely used in
applications such as binary search trees and heaps.
Example: Consider the tree below. Since each node of this tree has only 2 children, it can
be said that this tree is a Binary Tree.
Examples / Types of Binary Tree:
1. Expression Trees (Used in Compilers, Calculators)
Internal nodes: operators (+, -, *, /)
Leaf nodes: operands (2, 3, x)
Example:-
+
/\
3 *
/\
4 5
Represents: 3 + (4 * 5)
2. Binary Search Tree (BST) (Used in search systems, maps, sets)
Each left child < parent < right child.
Example:
10
/ \
5 20
/\ \
2 8 30
Allows fast search, insert, delete (O(log n) avg. case).
3. Decision Trees (Used in Machine Learning)
Nodes represent decisions or conditions.
Leaves represent outcomes.
Example:
IsRaining?
/ \
Yes No
/ \
TakeUmbrella WearSunglasses
4. Heaps (Binary Heap) (Used in priority queues)
A complete binary tree where every parent is greater/smaller than
children.
Used in algorithms like Dijkstra’s or Heap Sort.
5. File Systems / Hierarchical Structures
Though not strictly binary, parts of a file system tree can be modeled as
binary trees for traversal operations.
Python Code Example: Binary Tree Structure
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None
# Example binary tree
root = Node(10)
[Link] = Node(5)
[Link] = Node(20)
[Link] = Node(2)
[Link] = Node(8)
[Link] = Node(30)
2. Ternary Tree
A Ternary Tree is a tree data structure in which each node has at most three child nodes,
usually distinguished as “left”, “mid” and “right”.
Example: Consider the tree below. Since each node of this tree has only 3 children, it can
be said that this tree is a Ternary Tree.
Real-World Examples of Ternary Trees
1. Ternary Search Tree (TST)
Used for storing strings in search-intensive applications like dictionaries or autocomplete.
More space-efficient than a trie, and faster than binary search trees for string keys.
Example (Storing words like "cat", "bat", "rat"):
c
/|\
b a r
Each character is a node. Paths represent strings.
2. 3-Way Decision Trees
Used when each decision node has three possible outcomes.
Example: Loan Risk Classification
CreditScore
/ | \
Low Medium High
/ | \
Reject Manual Approve
Each branch from a node represents one of three distinct decisions.
3. Game AI Trees
In board games with 3 possible moves (e.g., Tic-Tac-Toe), a ternary tree can represent
states branching from a single point.
Example Tree:-
root = TernaryNode("Is temperature high?")
[Link] = TernaryNode("Yes")
[Link] = TernaryNode("Moderate")
[Link] = TernaryNode("No")
[Link] = TernaryNode("Turn on AC")
[Link] = TernaryNode("Do nothing")
[Link] = TernaryNode("Turn on heater")
3. N-ary Tree (Generic Tree)
Generic trees are a collection of nodes where each node is a data structure that consists of
records and a list of references to its children(duplicate references are not allowed). Unlike
the linked list, each node stores the address of multiple nodes.
Every node stores the addresses of its children and the very first node’s address will be stored
in a separate pointer called root.
1. Many children at every node.
2. The number of nodes for each node is not known in advance.
Examples of N-ary Trees:
Real-World Examples of N-ary Trees
1. File System Hierarchy
Directories (folders) can have many files or subfolders → an N-ary tree is a perfect model.
Root
├── Documents
│ ├── [Link]
│ └── [Link]
├── Music
│ ├── Rock
│ │ └── song1.mp3
│ └── Jazz
└── Pictures
├── Vacation
└── Birthday
2. HTML / XML Document Structure
Each HTML tag (e.g. <div>) can contain many child tags.
The DOM is an N-ary tree.
<html>
├── <head>
└── <body>
├── <h1>
├── <p>
└── <div>
├── <ul>
└── <img>
3. Company Organizational Chart
A CEO can have multiple direct reports (VPs), each with their own managers, etc.
CEO
├── VP1
│ ├── Manager1
│ └── Manager2
├── VP2
└── VP3
└── Manager3
4. Game Trees (e.g., Chess, Go, Tic-Tac-Toe)
Each node (board state) can have many possible moves → each move leads to a new
node.
5. Trie (Prefix Tree) — for word search/autocomplete
Technically a form of N-ary tree (each node has up to 26 children for alphabet).
Properties of Tree Data Structure:
Number of edges: An edge can be defined as the connection between two nodes. If a
tree has N nodes then it will have (N-1) edges. There is only one path from each node to
any other node of the tree.
Depth of a node: The depth of a node is defined as the length of the path from the root to
that node. Each edge adds 1 unit of length to the path. So, it can also be defined as the
number of edges in the path from the root of the tree to the node.
Height of a node: The height of a node can be defined as the length of the longest path
from the node to a leaf node of the tree.
Height of the Tree: The height of a tree is the length of the longest path from the root of
the tree to a leaf node of the tree.
Degree of a Node: The total count of subtrees attached to that node is called the degree
of the node. The degree of a leaf node must be 0. The degree of a tree is the maximum
degree of a node among all the nodes in the tree.
Basic Operations Of Tree Data Structure:
Create – create a tree in the data structure.
Insert − Inserts data in a tree.
Search − Searches specific data in a tree to check whether it is present or not.
Traversal:
Depth-First-Search Traversal
Breadth-First-Search Traversal
Tree Traversal
Tree Traversal refers to the process of visiting or accessing each node of the tree exactly
once in a certain order. Tree traversal algorithms help us visit and process all the nodes of
the tree. Since a tree is not a linear data structure, there can be multiple choices for the
next node to be visited. Hence we have many ways to traverse a tree.
There are multiple tree traversal techniques that decide the order in which the nodes of
the tree are to be visited. These are defined below:
[Link] First Search or DFS
In-order Traversal
Pre-order Traversal
Post-order Traversal
[Link] Order Traversal or Breadth First Search or BFS
In-order Traversal
In-order traversal visits the node in the order: Left -> Root -> Right
Algorithm for In-order Traversal
In-order(tree )
● Traverse the left subtree, i.e., call In-order(left->subtree)
● Visit the root.
● Traverse the right subtree, i.e., call In-order(right->subtree)
Uses of In-order Traversal
In the case of binary search trees (BST), In-order traversal gives nodes in non-
decreasing order.
To get nodes of BST in non-increasing order, a variation of In-order traversal where
In-order traversal is reversed can be used.
In-order traversal can be used to evaluate arithmetic expressions stored in
expression trees.
Pre-order Traversal
Pre-order traversal visits the node in the order: Root -> Left -> Right
Algorithm for Pre-order Traversal
Pre-order(tree)
● Visit the root.
● Traverse the left subtree, i.e., call Pre-order(left->subtree)
● Traverse the right subtree, i.e., call Pre-order(right->subtree)
Uses of Pre-order Traversal
Pre-order traversal is used to create a copy of the tree.
Pre-order traversal is also used to get prefix expressions on an expression tree.
Post-order Traversal
Post-order traversal visits the node in the order: Left -> Right -> Root
Algorithm for Post-order Traversal:
Post-order(tree)
●Traverse the left subtree, i.e., call Post-order(left->subtree)
● Traverse the right subtree, i.e., call Post-order(right->subtree)
● Visit the root
Uses of Post-order Traversal
Post-order traversal is used to delete the tree.
Post-order traversal is also useful to get the postfix expression of an expression tree.
Post-order traversal can help in garbage collection algorithms, particularly in
systems where manual memory management is used.
Level Order Traversal
Level Order Traversal visits all nodes present in the same level completely before visiting
the next level.
Algorithm for Level Order Traversal
Level Order(tree)
● Create an empty queue Q
● Enqueue the root node of the tree to Q
● Loop while Q is not empty
○Dequeue a node from Q and visit it
○ Enqueue the left child of the dequeued node if it exists
○ Enqueue the right child of the dequeued node if it exists .
Uses of Level Order Traversal
Level-wise node processing, like finding maximum/minimum at each level.
Tree serialization/deserialization for efficient storage and reconstruction.
Solving problems like calculating the “maximum width of a tree” by processing nodes level by
level.
Applications of Trees in Data Structures
The applications of trees in data structures are listed below:
Trees are ideal for hierarchical relationships between data elements such as file systems,
organizational charts, or XML/HTML documents.
Trees are used in databases to store and retrieve data for insertion, and deletion
operations.
Trie data structures are used for text processing tasks such as prefix matching, auto-
complete, and spell checking.
Spanning trees and shortest path trees are used in routers and bridges to efficiently route
data packets.
Expression Tree
The expression tree is a binary tree in which each internal node corresponds to the
operator and each leaf node corresponds to the operand so for example expression
tree for 3 + ((5+9)*2) would be:
In-order traversal of expression tree produces infix version of given postfix expression (same
with post-order traversal it gives postfix expression)
Examples:
Input: A B C*+ D/
Output: A + B * C / D
The first three symbols are operands, so create tree nodes and push pointers to them onto
a stack as shown below.
In the Next step, an operator ‘*’ will going read, so two pointers to trees are popped, a new tree is
formed and a pointer to it is pushed onto the stack
In the Next step, an operator ‘+’ will read, so two pointers to trees are popped, a new tree is
formed and a pointer to it is pushed onto the stack.
Similarly, as above cases first we push ‘D’ into the stack and then in the last step first, will read ‘/’
and then as previous step topmost element will pop out and then will be right subtree of root ‘/’
and other nodes will be right subtree.
Output
The In-order Traversal of Expression Tree: A + B * C / D
2. Graphs.
Introduction to Graphs: Types , Terminologies.
Graph Representation : Adjacency Matrix , Adjacency List
Basic Graph Algorithms: BFS , DFS.
Real-world Applications.
Graph Data Structure
Graph Data Structure is a non-linear data structure consisting of vertices and edges. It
is useful in fields such as social network analysis, recommendation systems, and
computer networks.
In the field of sports data science, graph data structure can be used to analyze and
understand the dynamics of team performance and player interactions on the field.
What is Graph Data Structure?
Graph is a non-linear data structure consisting of vertices and edges. The vertices are
sometimes also referred to as nodes and the edges are lines or arcs that connect any two
nodes in the graph. More formally a Graph is composed of a set of vertices( V ) and a set
of edges( E ). The graph is denoted by G(V, E).
Imagine a game of football as a web of connections, where players are the nodes and
their interactions on the field are the edges. This web of connections is exactly what a
graph data structure represents, and it’s the key to unlocking insights into team
performance and player dynamics in sports.
Components of Graph Data Structure
Vertices: Vertices are the fundamental units of the graph. Sometimes, vertices are also
known as vertex or nodes. Every node/vertex can be labeled or unlabelled.
Edges: Edges are drawn or used to connect two nodes of the graph. It can be ordered
pair of nodes in a directed graph. Edges can connect any two nodes in any possible
way. There are no rules. Sometimes, edges are also known as arcs. Every edge can be
labelled/unlabelled.
4. Degree of a Vertex
The Degree of a Vertex in a graph is the number of edges incident to that vertex. In a
directed graph, the degree is further categorized into the in-degree (number of incoming
edges) and out-degree (number of outgoing edges) of the vertex.
5. Path
A Path in a graph is a sequence of vertices where each adjacent pair is connected by an
edge. Paths can be of varying lengths and may or may not visit the same vertex more than
once. The shortest path between two vertices is of particular interest in algorithms such as
Dijkstra's algorithm for finding the shortest path in weighted graphs.
6. Cycle
A Cycle in a graph is a path that starts and ends at the same vertex, with no repetitions of
vertices (except the starting and ending vertex, which are the same). Cycles are essential
in understanding the connectivity and structure of a graph and play a significant role in
cycle detection algorithms.
Types Of Graphs in Data Structure and Algorithms
1. Null Graph
A graph is known as a null graph if there are no edges in the graph.
2. Trivial Graph
Graph having only a single vertex, it is also the smallest graph possible.
3. Undirected Graph
A graph in which edges do not have any direction. That is the nodes are unordered pairs
in the definition of every edge.
4. Directed Graph
A graph in which edge has direction. That is the nodes are ordered pairs in the definition
of every edge.
5. Connected Graph
The graph in which from one node we can visit any other node in the graph is known as
a connected graph.
6. Disconnected Graph
The graph in which at least one node is not reachable from a node is known as a
disconnected graph.
7. Regular Graph
The graph in which the degree of every vertex is equal to K is called K regular graph.
8. Complete Graph
The graph in which from each node there is an edge to each other node.
9. Cycle Graph
The graph in which the graph is a cycle in itself, the minimum value of degree of each
vertex is 2.
10. Cyclic Graph
A graph containing at least one cycle is known as a Cyclic graph.
11. Directed Acyclic Graph
A Directed Graph that does not contain any cycle.
12. Bipartite Graph
A graph in which vertex can be divided into two sets such that vertex in each set does
not contain any edge between them.
13. Weighted Graph
A graph in which the edges are already specified with suitable weight is known as a
weighted graph.
Weighted graphs can be further classified as directed weighted graphs and
undirected weighted graphs.
Representation of Graph Data Structure:
There are multiple ways to store a graph: The following are the most common
representations.
Adjacency Matrix
Adjacency List
Adjacency Matrix Representation of Graph Data Structure:
In this method, the graph is stored in the form of the 2D matrix where rows and columns
denote vertices. Each entry in the matrix represents the weight of the edge between those
vertices.
Adjacency List Representation of Graph:
This graph is represented as a collection of linked lists. There is an array of pointer which
points to the edges connected to that vertex.
Basic Operations on Graph Data Structure:
Below are the basic operations on the graph:
Insertion or Deletion of Nodes in the graph
Add and Remove vertex in Adjacency List representation of Graph
Add and Remove vertex in Adjacency Matrix representation of Graph
Insertion or Deletion of Edges in the graph
Add and Remove Edge in Adjacency List representation of a Graph
Add and Remove Edge in Adjacency Matrix representation of a Graph
Searching in Graph Data Structure- Search an entity in the graph.
Traversal of Graph Data Structure- Traversing all the nodes in the graph.
What are real-world applications of graphs?
Social Networks: Facebook, Twitter (users as vertices, connections as edges).
Google Maps: Locations as vertices, roads as edges with weights (distance/time).
Computer Networks: Routers as vertices, connections as edges.
Recommendation Systems: Netflix, Amazon (users and products as vertices, interactions
as edges).