Group 3

Presentation

1. TRESS
2. RECURSION
3. BACKTRACKING
TRESS
Introduction to Tree Data Structure
Tree data structure is a specialized data structure to store data in hierarchical manner. It is used to organize and store data in
the computer to be used more effectively. It consists of a central node, structural nodes, and sub-nodes, which are connected
via edges. We can also say that tree data structure has roots, branches, and leaves connected.

The data structure is called a "tree" because it looks like a tree, only upside down, just like in the image below.
The Tree data structure can be useful in many cases:
Hierarchical Data: File systems, organizational models, etc.
Databases: Used for quick data retrieval.
Routing Tables: Used for routing data in network algorithms.
Sorting/Searching: Used for sorting data and searching for data.
Priority Queues: Priority queue data structures are commonly
implemented using trees, such as binary heaps.
What is Tree Data Structure?
•Tree data structure is a hierarchical structure that is used to represent and organize data in a way that is easy to navigate and search.
It is a collection of nodes that are connected by edges and has a hierarchical relationship between the nodes.
•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.
Why is Tree 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 a non-linear data structure.
•Basic Terminologies In Tree Data Structure:
•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}.
•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. A non-empty tree must contain exactly one root node and exactly one path from the root to all other nodes of the
tree.
•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.
•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.
Neighbor 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.

Importance for Tree Data Structure:

1. One reason to use trees might be because you want to store information that naturally forms a hierarchy.
2. Trees (with some ordering e.g., BST) provide moderate access/search (quicker than Linked List and slower than
arrays).
3. Trees provide moderate insertion/deletion (quicker than Arrays and slower than Unordered Linked Lists).
4. Like Linked Lists and unlike Arrays, Trees don’t have an upper limit on the number of nodes as nodes are linked
using pointers.
Types of Tree data structures:
Tree data structure can be classified into three types based upon the number of children each node
of the tree can have. The types are:
Binary tree: In a binary tree, each node can have a maximum of two children linked to it. Some
common types of binary trees include full binary trees, complete binary trees, balanced binary
trees, and degenerate or pathological binary trees.
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”.
N-ary Tree or 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.
Binary trees are a fundamental data structure in computer science, characterized by each node
having at most two children, referred to as the left child and the right child. Here are some key
concepts and properties related to binary trees:
1.Node: The fundamental part of a binary tree, which contains a value or data and pointers to its
children.
2.Root: The topmost node of a binary tree. It is the starting point for traversals.
3.Leaf: A node that has no children. It is the endpoint for paths in the tree.
4.Internal Node: A node that has at least one child.
5.Height: The length of the longest path from the root to a leaf. A tree with a single node (the
root) has a height of
6. Depth: The length of the path from the root to a particular node. The root has a depth of
7.Subtree: Any node along with its descendants forms a subtree.
8.Traversal:
o Pre-order Traversal: Visit the root, then the left subtree, and finally the right subtree.
o In-order Traversal: Visit the left subtree, the root, and then the right subtree.
o Post-order Traversal: Visit the left subtree, the right subtree, and then the root.
o Level-order Traversal: Visit nodes level by level, starting from the root.
 7.Types of Binary Trees:
o Full Binary Tree: Every node has either 0 or 2 children.
o Perfect Binary Tree: All internal nodes have two children, and all leaves are at the same
level.
o Complete Binary Tree: All levels are fully filled except possibly for the last level,
which is filled from left to right.
o Balanced Binary Tree: The height of the left and right subtrees of any node differ by
almost one.
o Binary Search Tree (BST): A binary tree where for every node, all nodes in its left
subtree have smaller values, and all nodes in its right subtree have larger values.
8.Applications:
o Binary Search Trees (BSTs): Efficient for search, insert, and delete operations.
o Heaps: Binary trees used to implement priority queues.
o Expression Trees: Used in compilers and calculators to represent expressions.
o Decision Trees: Used in machine learning for classification and regression tasks.
Understanding these basic concepts and properties is essential for working with binary trees and
applying them to various computational problems.
 Basic Operations Of Tree Data Structure:
1.Create – create a tree in the data structure.
2. Insert − Inserts data in a tree.
3. Search − Searches specific data in a tree to check whether it is present or not.
4. Traversal:
Depth-First-Search Traversal
Breadth-First-Search Traversal
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.
Advantages of Tree Data Structure:
 Tree offers Efficient Searching Depending on the type of tree, with average search times of O(log n) for balanced
trees like AVL.
 Trees provide a hierarchical representation of data, making it easy to organize and navigate large amounts of
information.
 The recursive nature of trees makes them easy to traverse and manipulate using recursive algorithms.

Disadvantages of Tree Data Structure:

 Unbalanced Trees, meaning that the height of the tree is skewed towards one side, which can lead to inefficient
search times.
 Trees demand more memory space requirements than some other data structures like arrays and linked lists,
especially if the tree is very large.
 The implementation and manipulation of trees can be complex and require a good understanding of the
algorithms.
RECURSION
 Recursion
Recursion in data structure can be defined as a method through which problems are broken down into smaller sub-
problems to find a solution. This is done by replicating the function on a smaller scale, making it call itself, and then
combining them together to solve problems. It entails decomposing a challenging issue into more manageable issues
and then solving each one again.

Recursive Function
A recursive function is a function that solves a problem by solving smaller instances of the same problem.
This technique is commonly used in programming to solve problems that can be broken down into
simpler, similar subproblems.

Properties of Recursion
It solves a problem by breaking it down into smaller sub-problems, each of which can be solved in the same way.
A recursive function must have a base case or stopping criteria to avoid infinite recursion.
Recursion involves calling the same function within itself, which leads to a call stack.
Recursive functions may be less efficient than iterative solutions in terms of memory and performance.
 TYPES OF RECURSION
A) Direct Recursion

Direct recursion is a type of recursion in which a function

directly calls itself during its execution. The function solves a
smaller subproblem and then calls itself with the reduced
subproblem until it reaches a base case that terminates the
recursion. Direct recursion involves a straightforward and
explicit self-reference within the function’s body.

Advantages

Simplicity: Direct recursion often provides a

straightforward and intuitive solution for problems
that exhibit self-similar subproblems.

Readability: Recursive functions can often

express the problem-solving logic more clearly and
concisely, making the code easier to understand.
Disadvantage

•Memory Usage: Recursive function calls consume memory as each call

creates a new stack frame. If the recursion depth is large, it may lead to stack
overflow errors.

•Performance Overhead: Recursive calls involve function call overhead, which

can impact performance compared to iterative approaches.

•Tail Recursion Optimization: Direct recursion may not benefit from tail
recursion optimization, where the recursive call is the last operation in the
function. This optimization eliminates the need for maintaining multiple stack
frames, enhancing performance.

B) Indirect Recursion

Indirect recursion is a type of recursion in which a function calls another

function(s). The chain of function calls leads back to the original function,
creating a cycle. In indirect recursion, there is a circular dependency among
multiple functions, where each function calls another function(s) in a sequence
until the base case is reached.

Advantages

•Problem Decomposition: Indirect recursion can be useful for breaking down a

complex problem into smaller, interdependent subproblems. Each function
focuses on solving a specific part of the problem.

•Code Modularity: By dividing the problem-solving logic across multiple

functions, the code can be organized and modularized, improving readability
Disadvantages

•Complexity: Indirect recursion can introduce additional complexity due to the interdependencies between functions. This complexity can
make code harder to understand and debug.

•Execution Order: The execution order of functions in indirect recursion is crucial. Incorrect sequencing or missing base cases can lead to
infinite loops or incorrect results.

•Performance Overhead: Similar to direct recursion, indirect recursion can incur function call overhead and memory consumption. Care
must be taken to avoid excessive recursive calls.

Recursion method in data structure

1. Tail recursion is a specific form of recursion where the recursive call is the last operation performed in a function. In other words, there is
no pending computation after the recursive call.

2. Binary recursion involves dividing a problem into two smaller subproblems and solving each subproblem separately. The results of the
subproblems are then combined to obtain the final solution.

3. Linear recursion refers to a recursive approach where a problem is divided into a single subproblem. Each recursive call reduces the
problem size by a constant factor until a base case is reached, which terminates the recursion. Linear recursion is often used when
solving problems that can be broken down into smaller, similar instances.

4. Mutual recursion is a form of recursion where two or more functions call each other in a cyclic manner. These functions work together to
solve a problem by dividing it into subproblems, which are then solved using the corresponding mutually recursive functions.

5. Nested recursion occurs when a recursive function calls itself with a recursive call as one of its arguments. In other words, the input
parameter of the recursive call is the result of another recursive call.

6. recursive algorithm is an algorithmic approach that solves a problem by breaking it down into smaller subproblems of the same kind.
Advantages of Recursion
1. Clarity and simplicity: Recursion can make code more readable and easier to understand. Recursive
functions can be easier to read than iterative functions when solving certain types of problems, such as
those that involve tree or graph structures.
2. Reducing code duplication: Recursive functions can help reduce code duplication by allowing a
function to be defined once and called multiple times with different parameters.
3. Solving complex problems: Recursion can be a powerful technique for solving complex problems,
particularly those that involve dividing a problem into smaller subproblems.
4. Flexibility: Recursive functions can be more flexible than iterative functions because they can handle
inputs of varying sizes without needing to know the exact number of iterations required.
Disadvantages of Recursion
5. Performance Overhead: Recursive algorithms may have a higher performance overhead compared to
iterative solutions. This is because each recursive call creates a new stack frame, which takes up
additional memory and CPU resources. Recursion may also cause stack overflow errors if the recursion
depth becomes too deep.
6. Difficult to Understand and Debug: Recursive algorithms can be difficult to understand and debug
because they rely on multiple function calls, which can make the code more complex and harder to
follow.
7. Memory Consumption: Recursive algorithms may consume a large amount of memory if the recursion
depth is very deep.
8. Limited Scalability: Recursive algorithms may not scale well for very large input sizes because the
recursion depth can become too deep and lead to performance and memory issues.
9. Tail Recursion Optimization: In some programming languages, tail recursion optimization is not
BACKTRACKING
Backtracking is a problem-solving algorithmic technique that involves finding a solution incrementally by trying different options
and undoing them if they lead to a dead end.
When a dead end is reached, the algorithm backtracks to the previous decision point and explores a different path until a solution is
found or all possibilities have been exhausted.
A backtracking algorithm works by recursively exploring all possible solutions to a problem. It starts by choosing an initial solution,
and then it explores all possible extensions to that solution. If an extension leads to a solution, the algorithm returns that solution. If an
extension does not lead to a solution, the algorithm backtracks to the previous solution and tries a different extension.

General outline
Choose an initial solution.
Explore all possible extensions of the current solution.
If an extension leads to a solution, return that solution.
If an extension does not lead to a solution, backtrack to the previous solution and try a different extension.
Repeat steps 2-4 until all possible solutions have been explored.

Backtracking is generally used for three types of problems:

Decision problem - Searching for a feasible solution.
Decision problems in data structures and algorithms are those that can be answered with a simple yes or no answer. These problems
often involve determining the properties of data or the feasibility of certain operations within an algorithm. Here are some common
examples:
o Graph Theory: Given a graph and two nodes, is there a path between them?
o Sorting: Is a given list already sorted?
o Searching: Does a given element exist in a specific data structure (like an array or tree)?
2. Optimization problems in data structures and algorithms deal\ with finding the best possible solution among all
feasible options. Unlike decision problems that ask for a yes/no answer, these problems aim to minimize or maximize a
certain value. Here are some classic examples of optimization problems in this domain:
o Shortest Path Finding: Given a graph and two nodes, what's the shortest path for traveling between them?
o Minimum Spanning Tree: In a connected graph, what's the subset of edges that connects all nodes with the least
total weight?
o Knapsack Problem: Given a knapsack with a weight limit and a set of items with weights and values, how can you
fill the knapsack to maximize the total value of items without exceeding the weight limit?
o Job Scheduling: Given a set of jobs with varying processing times and deadlines, how can you schedule them on a
single machine to minimize the total completion time?
3. Enumeration problems (Searching for all feasible solutions) in data structures and algorithms deal with finding and
listing all possible solutions for a given input, rather than just finding one solution or determining if a solution exists.
Here are some common examples:
o Graph algorithms: Finding all possible paths between two nodes in a graph, enumerating all connected components
in a graph, or listing all cliques (complete subgraphs) within a graph.
o Combinatorics: Generating all permutations (arrangements) or combinations (selections) of a set of elements.
o String algorithms: Listing all possible substrings of a given string or finding all occurrences of a pattern within a
string.
Difference between recursion and backtracking
Recursion Backtracking
Recursion does not always need Backtracking always uses recursion
Backtracking tosolve problems
A recursive function solves a particular Backtracking at every step eliminates
problem by calling a copy of itself and those choices that cannot give us the
solving smaller subproblems of the solution and proceeds to those choices
original problems. that have the potential of taking us to
the solution.
Recursion is a part of backtracking Backtracking is comparatively complex
itself and it is to
simpler to write. implement.

Applications of Backtracking
1. Creating smart bots to play Board Games such as Chess
 Suppose we are coding a chess-playing algorithm and at a certain point, the algorithm finds that a set of steps
fails to win. In this situation, the algorithm will reverse back to the safe state and try another possible set of
steps.
2. Solving mazes and puzzles such as N-Queen problem.
 The idea is to place queens one by one in different columns, starting from the leftmost column. When we place a queen in a
column, we check for clashes with already placed queens. In the current column, if we find a row for which there is no clash, we
mark this row and column as part of the solution. If we do not find such a row due to clashes, then we backtrack and return false.

3. Network Routing and Congestion Control.

 Backtracking is used in network optimization to find the best path on a network to forward packets in order to reduce latency,
bandwidth and to improve network efficiency and reliability.
 Here's how it works:
o Imagine a network as a maze, where nodes represent devices and connections represent paths.
o A backtracking algorithm can systematically explore different paths in the network, evaluating metrics like bandwidth, latency,
or cost.
o As it explores a path, it keeps track of the current performance and discards paths that exceed certain constraints or become less
promising.
o By backtracking from dead ends and exploring promising branches, the algorithm can eventually find the optimal route that
meets the desired criteria.
This technique is particularly applicable in scenarios like:
o Traffic routing: Optimizing how data packets flow through a network to avoid congestion and ensure efficient delivery.
o Resource allocation: Assigning bandwidth, storage, or other resources to network devices to meet performance requirements.
o Network design: Determining the placement of network elements like routers and switches to create a cost-effective and high-
performing network infrastructure.
4. Decryption
Backtracking can be a useful technique in cryptanalysis, which is the art of breaking codes.
Here's how it can be applied in decryption:
o Exhaustive key search: In some ciphers, particularly weak ones, backtracking can be used to try every possible
decryption key until the correct one is found. This is a brute-force approach that can be slow, but it's guaranteed to
succeed for certain types of ciphers.
o Constraint satisfaction: Backtracking can be used to exploit known weaknesses or constraints in a cipher. By
systematically trying different key values and analyzing the resulting plaintext for patterns or inconsistencies, the
algorithm can gradually narrow down the possibilities and identify the most likely key.

5. Text Justification
Backtracking can be a technique used in text justification, but it's not the most common approach due to its
computational complexity. Here's a brief explanation:
o Text justification aims to arrange words in lines of a fixed width, adding spaces strategically to create a balanced
and visually appealing layout.
o Backtracking would involve trying various ways to insert spaces between words in a line. It would explore different
possibilities by inserting spaces in different places and evaluating the resulting line breaks and spacing distribution.
The algorithm would need to backtrack from unsuccessful attempts, trying alternative space insertions until it finds a
configuration that meets the justification criteria (e.g., minimal raggedness, even spacing distribution).
Advantages of backtracking
Backtracking offers several advantages as a problem-solving approach:
 Completeness: It ensures that all possible valid solutions are explored, making it useful for the search for optimal solutions.
 Efficiency: Backtracking can be very effective, especially in problems with strong constraints, enabling certain options to be
quickly eliminated.
 Adaptability: It can be applied to a variety of problems, as it is based on a general tree structure.
The limits of backtracking
Despite its advantages, backtracking has certain limitations:
 Combinatorial explosion: In some problems, the number of combinations to be explored can increase exponentially, as in the
case of the travelling salesman problem, where if a path is calculated in 1 microsecond, it takes almost two millennia to calculate
all the paths passing through 20 points.
 Complexity: The implementation of backtracking can be complex, especially in problems where the definition of choices,
constraints and stopping criteria is complicated.
 No guarantee of convergence: Backtracking may not converge to a solution in some cases, for example when the solution
doesn’t exist, or get stuck in infinite loops if the problem is poorly defined.
Optimizing backtracking
There are several techniques for optimizing the backtracking process, including :
 Heuristics: The use of intelligent rules and heuristics to guide the search to the most promising branches of the decision tree.
 Pruning: The identification and early elimination of certain branches of the tree that cannot lead to a solution, thus reducing
combinatorial explosion.
 Memory: Caching of explored states to avoid recalculating the same configurations several times when they can be obtained in
several different ways.
Thank you
ANY QUESTIONS