Unit - IV

Introduction to Tree Data Structure

• Definition:

• A tree is a hierarchical data structure consisting of nodes connected by

edges.

• It is a definite set of one or more nodes,

• It is a specialized form of a graph with no cycles, ensuring a unique path

between any two nodes.

• A tree is defined recursively:

• It consists of a root node and zero or more subtrees, each of which is also a tree.
• Basic Terminologies In Tree Data Structure:

• Parent 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}.

• 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}.

• Root 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.

• Leaf 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.
• 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: A node x is a descendant of another node y if and only if y is an ancestor
of x.
• Sibling: Children of the same parent node are called siblings. {D,E} are called
siblings.
• Level of a node: The count of edges on the path from the root node to that node. The
root node has level 0.
• Internal node: A node with at least one child is called Internal Node.
• 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.
Binary Tree
• Binary Tree is a non-linear and hierarchical data structure where each
node has at most two children referred to as the left child and the right
child.

• The topmost node in a binary tree is called the root, and the bottom-most
nodes are called leaves.
• Properties of Binary Trees
[Link] of Nodes:
1. Maximum nodes at level : (0-based index).
2. Maximum nodes in a binary tree of height : .

[Link] of Tree:
1. Number of edges on the longest path from the root to a leaf.

[Link] of Binary Trees:

1. Full Binary Tree: Every node has 0 or 2 children.
2. Complete Binary Tree: All levels except the last are fully filled, and nodes are as left as possible.
3. Perfect Binary Tree: All internal nodes have two children, and all leaves are at the same level.
4. Balanced Binary Tree: Difference in height between left and right subtrees is at most 1 for all nodes.

[Link] Methods:
1. In-order: Left → Root → Right.
2. Pre-order: Root → Left → Right.
3. Post-order: Left → Right → Root.
• Representation of Binary Tree
1. Linear Representation of a Binary Tree

• Array Representation:
• Store nodes in an array.

• Indexing:
• Root at index 0.

• Left child of node at index : .

• Right child of node at index : .

2. Linked Representation of a Binary Tree
•Each node contains:
• Data field: Stores the value.
• Pointer to the left child.
• Pointer to the right child.
Physical Implementation of a Binary Tree in Memory

• Physical implementation determines how binary trees are stored in memory

for efficient operations.

• Two Primary Methods:

• Array based Representation

• Pointer based Representation(linked list)

Pointer-Based Representation

• Each node in the binary tree is a structure consisting of three components:

• A field to store data or key value.

• A pointer to the left child.

• A pointer to the right child.

• How It Works:

• The tree starts with a root node stored in memory.

• Each node is dynamically allocated in memory as needed.

• The left and right pointers in each node establish links to their respective child
nodes.
Array-Based Representation
•The binary tree is stored in a linear array.
•The root of the tree is placed at the first index of the array.
•For any node at index i:
•The left child is stored at index 2*i + 1.
•The right child is stored at index 2*i + 2.
•If a node does not have a child, the corresponding index remains empty or
stores a placeholder value (e.g., null or -1).
Traversing binary tree
• A Tree Data Structure can be traversed in following ways:
• Depth First Search or DFS
• Inorder Traversal
• Preorder Traversal
• Postorder Traversal
Inorder Traversal
• Inorder traversal visits the node in the order: Left ->
Root -> Right.
• Preorder Traversal:
• Preorder traversal visits the node in the order: Root ->
Left -> Right
Postorder Traversal:
• Postorder traversal visits the node in the order: Left ->
Right -> Root
Binary Search Tree
A Binary Search Tree (BST) is a type of binary tree where each node follows
the binary search property:

[Link] left subtree of a node contains only nodes with keys smaller than the
node’s key.

[Link] right subtree of a node contains only nodes with keys greater than the
node’s key.

[Link] the left and right subtrees must also be binary search trees.
S
Algorithm to search for a key in a given Binary Search Tree:
We compare the value to be searched with the value of the root.
If it’s equal we are done with the search.
If it’s smaller we know that we need to go to the left subtree because in a binary
search tree all the elements in the left subtree are smaller and all the elements in the
right subtree are larger.
Repeat the above step till no more traversal is possible.
Threaded Binary Tree
• A threaded binary tree is a type of binary tree data structure where the empty
left and right child pointers in a binary tree are replaced with threads.

• Types of Threaded Binary Tree

There are two types of threaded Binary Tree:

• One-way threaded Binary Tree

• Two-way threaded Binary Tree

 One-way threaded binary trees
• If it appears in the right link field of a node then it will point to the
next node that will appear on performing inorder successor traversal.
Such trees are called Right threaded binary trees.

• If thread appears in the left field of a node then it will point to the
nodes inorder predecessor. Such trees are called Left threaded binary
trees.
Two-way threaded Binary trees
• In two-way threaded Binary trees, the right link field (if a node does not
have a right child, its right pointer is replaced with a thread. This thread
points to the in-order successor of the node.

• Left Link Field: If a node does not have a left child, its left pointer is
replaced with a thread. This thread points to the in-order predecessor of the
node.

• In-order Successor: The next node in the in-order traversal of the tree.

• In-order Predecessor: The previous node in the in-order traversal of the tree.
 Height-balanced binary tree
• A height-balanced binary tree is defined as a binary tree in which
the height of the left and the right subtree of any node differ by not
more than 1.
Eg: AVL tree, red-black tree are examples of height-balanced trees.

Note: An empty tree is also height-balanced.

Explanation: The height difference between the left and right subtrees at node 2
is 2, which exceeds 1. Hence, the tree is not balanced.
What is the Height Balance of a node?

• To check if the binary tree is height-balanced or not, you have to check the
height balance of each node.

• To calculate the heights of the two subtrees for each node making this
impractical.

• The height balance of a node is calculated as follows:

height balance of node = height of right subtree – height of left subtree

The above formula means that:
• If the right subtree is taller, the height balance of the node will be positive.

• If the left subtree is taller, the balance of the node will be negative.
Conditions

[Link] if the absolute height difference between the left and right subtrees is
greater than 1.

[Link] the difference is less than or equal to 1, check if the left and right subtrees are
also balanced.

[Link] the left and right subtrees are balanced, the tree is height-balanced.

[Link] any of the above conditions fail, the tree is not height-balanced.
 Decision tree
• Decision tree is a simple diagram that shows different choices and
their possible results helping to make decisions easily.

• A decision tree is a graphical representation of different options for

solving a problem and show how different factors are related.

• It has a hierarchical tree structure starts with one main question at the
top called a node.
• Root Node is the starting point that represents the entire dataset.

• Branches: These are the lines that connect nodes. It shows the flow
from one decision to another.

• Internal Nodes are Points where decisions are made based on the
input features.

• Leaf Nodes: These are the terminal nodes at the end of branches that
represent final outcomes or prediction.
How Decision Trees Work?

• A decision tree working starts with a main question known as the root node.

• From the root node, the tree asks a series of yes/no questions. Each question is designed to

split the data into subsets based on specific attributes.

• Depending on the response to each question you follow different branches. If your answer is

“Yes,” you might proceed down one path if “No,” you will take another path.

• This branching continues through a sequence of decisions. As you follow each branch, you get

more questions that break the data into smaller groups. This step-by-step process continues

until you have no more helpful questions .

• You reach at the end of a branch where you find the final outcome or decision. It could be a

classification (like “spam” or “not spam”) or a prediction (such as estimated price).

Classification of Decision Tree

• We have mainly two types of decision tree based on the nature of the target
variable: classification trees and regression trees.

• Classification trees: They are designed to predict categorical outcomes means

they classify data into different classes. They can determine whether it is
“spam” or “not spam” based on various features.

• Regression trees : These are used when the target variable is continuous It
predict numerical values rather than categories. For example a regression tree
can estimate the price of a house based on its size, location, and other features.
 Graph
• 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).

1. Graph
Basic Graph Terminology
• A Graph G is a non-empty set of vertices (or nodes) V and a set of edges E, where each edge connects a
pair of vertices. Formally, a graph can be represented as G= (V, E).
• Graphs can be classified based on various properties, such as directedness of edges and connectivity.

2. Vertex (Node)

• A Vertex, often referred to as a Node, is a fundamental unit of a graph. It represents an entity within the
graph.
• In applications like social networks, vertices can represent individuals, while in road networks, they can
represent intersections or locations.

3. Edge

• An Edge is a connection between two vertices in a graph. It can be either directed or undirected. In a
directed graph, edges have a specific direction, indicating a one-way connection between vertices.
• In contrast, undirected graphs have edges that do not have a direction and represent bidirectional
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.
 Advanced Graph Terminology
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. Cyclic Graph

• A graph containing at least one cycle is known as a Cyclic graph.

10. Directed Acyclic Graph

• A Directed Graph that does not contain any cycle.

11. 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.
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
• 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.
 Operations on Graph
• The primary operations of a graph include creating a graph with vertices and
edges, and displaying the said graph.

• However, one of the most common and popular operation performed using
graphs are Traversal, i.e. visiting every vertex of the graph in a specific order.

• There are two types of traversals in Graphs −

• Depth First Search Traversal

• Breadth First Search Traversal

 Applications of Graph
• Seminar