Tree

Algorithm to Count Leaf Nodes in a Binary Tree

1. If the node is NULL, return 0.

2. If both left and right children are NULL, return 1 (it's a leaf).
3. Otherwise, recursively count leaf nodes in both subtrees:

Leaf count = Leaf count of left subtree + Leaf count of right subtree

General Tree-Search Algorithm

1. Initialise the frontier with the initial state of the problem.

2. Loop until a solution is found or failure:
a. If the frontier is empty, return failure.
b. Choose a leaf node from the frontier.
c. If the node is a goal state, return the solution.
d. Expand the node and add resulting nodes to the frontier.

Graph Search Algorithm

1. Initialise the frontier with the initial state and the explored set as empty.
2. Loop until a solution is found or failure:
a. If the frontier is empty, return failure.
b. Choose a leaf node from the frontier and remove it.
c. If the node is a goal state, return the solution.
d. Add the node to the explored set.
e. Expand the node, adding only resulting nodes not in the frontier or explored
set.

What is a Graph search algorithm?

Graph searching is a set of algorithms for traversing or exploring nodes (vertices) and edges
in a graph. These algorithms help find specific nodes, paths, or check properties within a
graph, such as connectivity or cycles. The two primary types of graph search algorithms are
Depth-First Search (DFS) and Breadth-First Search (BFS).

Two search strategies?

1) Uninformed(BFS, DFS etc.) : Uninformed search means that the strategies have no
additional information about states beyond that provided
in the problem definition.

2) Informed(Best first, Heuristic): Informed search strategies use information about

the problem (estimated distance from a state to the goal) to guide the search.
 BFS(Breadth First Search)

What is BFS?

Breadth-First Search (BFS) is a graph traversal algorithm that explores nodes level by
level. Starting from a given node, BFS visits all neighbouring nodes before moving on to the
neighbours of those nodes. It systematically explores the graph, ensuring that nodes closest
to the starting node are visited first.

Characteristics:

1. Level-order Traversal: BFS explores all nodes at the current level before moving to
the next level.
2. Queue-based: BFS uses a queue (FIFO) data structure to keep track of nodes that
need to be explored.
3. Unweighted Graphs: BFS is useful for finding the shortest path in an unweighted
graph, as it always finds the minimum number of edges from the start node to the
goal node.
***Algorithm of BFS for tree search (previous year ):

Initialise the Queue: Create an empty queue and enqueue the root node of the tree.

Start BFS Loop:

● While the queue is not empty:

● Dequeue the Front Node: Remove the front node from the queue (this is the current
node).
● Process the Node: Perform any required operation on the current node (e.g.,
printing its value or storing it in a result list).
● Enqueue Child Nodes: Add all unvisited children of the current node to the queue
(from left to right if it's a binary tree).

End Condition:

The loop stops when there are no more nodes in the queue, meaning all nodes have been
visited level-by-level.

Pseudocode:

Applications:

● Finding the shortest path in an unweighted graph.

● Checking if a graph is connected.
● Solving puzzles like mazes.
Ex:

Advantages:

• BFS provides a solution if any solution exists.

• If there are more than one solutions for a given problem, then BFS provides the minimal
solution which requires the least number of steps.

Disadvantages or limitations :

• It requires lots of memory since each level of the tree must be saved into memory to
expand the next level.

• BFS needs lots of time if the solution is far away from the root node.

Performance Evaluation of Searching Algorithm

We can evaluate an algorithm’s performance in four ways:

1) Completeness: Is the algorithm guaranteed to find a

solution when there is one?

2) Optimality: Does the strategy find the optimal solution?

Breadth-first search is optimal if the path cost is a nondecreasing function of the depth of the
node.

3) Time complexity: How long does it take to find a solution? Guaranteed to find the least
cost path? Time is often measured in terms of the number of nodes
generated during the search.

4) Space complexity: How much memory is needed to perform the search? Space in terms
of the maximum number of nodes stored in memory.

Q: How is BFS not optimal? and When is it optimal? And Conditions of Optimality of
BFS.
BFS does not always guarantee an optimal solution if the step costs vary. This is because
BFS only minimizes the number of steps (or depth of nodes) rather than the path cost.

BFS is optimal when

1. All Step Costs are Equal
2. Step Costs Increase Consistently with Depth

EX:
BFS is Not optimal for the graph but if all weight are same or increasing manner then it will
be optimal.

DFS(Depth First Search)

Depth-First Search (DFS) is an algorithm for traversing or searching tree or graph structures.
Starting from a root node, DFS explores as far as possible along each branch before
backtracking.

Depth-First Search (DFS) Algorithm

1. Initialise an empty stack (or use recursion) and an empty set for visited nodes.
2. Push the starting node (root) onto the stack.
3. While the stack is not empty:
a. Pop the top node from the stack.
b. If the node has not been visited:
● Mark it as visited.
● Process the node (e.g., print it, or check if it is a goal).
● Push all unvisited neighbours of the node onto the stack.
Pseudocode:

Ex:

Dfs:

Time complexity : O(b^m) →

b is the branching factor(The branching factor is simply the number of "branches" or
possible choices we have at each step in a search tree.)

m = maximum depth of any node;

Space complexity: O(bm)

Completeness:

Q: Why DFS is incomplete.?

There are two reasons

(a) There is a possibility of a loop. It can be fixed within the cycles and can make a loop
resulting in no solution.
(b) Another is that there may be infinite space. So it will go deepest (infinite space/nodes)
resulting
no solution.

Advantages:

1) Less memory than bfs.

 2) Easily implemented using recursion

Disadvantages:

1) Doesn’t necessarily find the shortest path while bfs does

2) Sometimes it may go infinite loop
3) There is the possibility that many states keep reoccurring, and there is no guarantee
of finding the solution.

Q: Difference between BFS vs DFS?

Uninformed Cost search

Uniform Cost Search (UCS) is an uninformed search algorithm often used in AI and
pathfinding. It operates by expanding the node with the least cumulative cost, making it
particularly effective for finding the shortest path in a weighted graph.

Q: Can we guarantee optimality for any step cost?

Uniform Cost Search (UCS) guarantees optimality only if all step costs are non-negative.
This is because UCS expands the least-cost paths first, ensuring the first path to the goal is
the shortest. However, with negative step costs, UCS can’t guarantee an optimal solution
and may even enter infinite loops by repeatedly taking negative-cost edges. For graphs with
negative weights, algorithms like Bellman-Ford are more suitable as they can handle
negative costs and still find optimal paths.
Algorithm:

Initialize:

● Create an empty priority queue to store nodes with their path cost.
● Add the start node to the queue with a path cost of 0.
● Create an empty set to track visited nodes.

Loop:

● While the queue is not empty:

○ Remove the node with the lowest path cost.
○ If this node is the goal, return the path and total cost.
○ Mark the node as visited.
○ For each neighbour:
■ Calculate the new path cost.
■ If the neighbour is unvisited or has a lower recorded cost, add it to the
queue with the updated cost.

End:

● If the queue empties without finding the goal, return “no solution.”

Advantages

1. Optimality: Guarantees the least-cost path to the goal.

2. Completeness: Always finds a solution if one exists (with non-negative costs).
3. Versatile: Works with varying path costs.

Disadvantages

1. High Time Complexity: Can explore many nodes, especially in large graphs.
2. High Space Complexity: Stores all generated nodes in memory.
3. Slower in Uniform Costs: Less efficient than BFS for uniform cost graphs.
4. Sensitive to Edge Weights: Performance can degrade with many low-cost edges.

Greedy Search

Greedy Best First Search:

Greedy best-first search tries to expand the node that is closest to the goal, on the grounds
that this is likely to lead to a solution quickly.

Also called Best-First search or Greedy search

Algorithm:
Let ‘OPEN’ be a priority containing the initial state.
Loop
if OPEN is empty return failure

Node Remove-First (OPEN)

if Node is a Goal
then return the path from initial to Node

else generate all successors of Node and put the

newly generated Node into OPEN according to their
f values // here f value means heuristic value
END Loop

EX:
Advantages

1. Fast Search: Quickly finds solutions by prioritising nodes near the goal.
2. Low Space Complexity: Requires less memory than other algorithms.
3. Simple Implementation: Easy to code due to its heuristic nature.

Disadvantages

1. Not Optimal: Can find suboptimal solutions.

2. Incompleteness: May miss solutions in complex graphs.
3. Heuristic Dependence: Relies on the quality of the heuristic.
4. Local Minima: Can get stuck, leading to inefficient paths.

Alpha Beta Algorithm

Alpha-Beta Pruning is an optimization technique for the minimax algorithm, commonly used
in decision-making and game theory, especially in two-player games like chess or tic-tac-toe.
Its main goal is to reduce the number of nodes that are evaluated by the minimax algorithm,
which can significantly improve its efficiency.

**(Previous year 1):

 1. At Node B (Min Level):
○ We check Nodes E, F, and G with values 8, 7, and −4.
○ β becomes −4 at Node B, so Node A (Max) now has α= −4
2. At Node C (Min Level):
○ We check Nodes H and I with values 5 and 5.
○ β at Node C is 5, so Node A updates α=5 .
3. At Node D (Min Level):
○ With α=5 at Node A, we don’t need to check Nodes J, K, and L under Node
D because they can’t give a better result.

Result: The optimal value for Node A is 5, and we skipped Nodes J, K, and L, making the
process faster.

**(Previous year 2)

Answer: Left subtree is the path because it gives me 3 as the max result.

Q: How to improve the effectiveness of alpha beta pruning?

Effectiveness depends on move order: Evaluating high-potential moves first improves

pruning efficiency.

Better Move Order = More Pruning: Proper move ordering significantly reduces the
number of nodes evaluated.

Advantages:

● Faster: Reduces nodes to evaluate, speeding up the Minimax algorithm.

● Better Decisions: Allows deeper searches for better moves.
● Resource-Efficient: Saves memory and computing power.

Disadvantages:

● Order-Dependent: Works best if good moves are checked first.

 ● Limited Use: Mostly for two-player games.
● Complexity: Adds some complexity to basic Minimax.

A* search Algorithm

A* (A-star) is a popular pathfinding and graph traversal algorithm used in computer science
and AI for finding the shortest path between two points. It combines the advantages of
Dijkstra’s Algorithm and Greedy Best-First Search by considering both the cost to reach a
node and the estimated cost to get from that node to the goal.

A* uses two main components to calculate the cost of reaching nodes:

1. G(n): The actual cost from the start node to the current node n.
2. H(n): A heuristic estimate of cost.

The algorithm combines these to form a score:

F(n)=G(n)+H(n)

Algorithm:

1) Initialize: Add the starting node to an open list (priority queue based on F(n)F(n)F(n)
values).
2) Loop Until Goal is Found:
● Take the node with the lowest F(n) from the open list.
○ If it's the goal node, return the path.
○ Otherwise, for each neighbor:
■ Calculate F(n) for the neighbor.
■ If this path is better than any previously recorded path to the neighbor,
update it and add the neighbor to the open list.
3) Repeat until the open list is empty or the goal is found.
Advantages

● A* search algorithm is the best algorithm than other search algorithms.

● A* the search algorithm is optimal and complete.
● This algorithm can solve very complex problems.

Disadvantages

● It does not always produce the shortest path as it is mostly based on heuristics and
approximation.
● A* The search algorithm has some complexity issues.
● The main drawback of A* is memory requirement as it keeps all generated nodes in
the memory, so it is not practical for various large-scale problems.

Applications

● Pathfinding in games (e.g., NPC navigation)

● Robot movement planning
 ● GPS route optimization

Q: Comparison between Uniform Cost search (UC) and A* search.

Previous Year:
Answer:

Function for A* algorithm:

Function(Queue) →

1. Let OPEN be a priority queue containing the initial state

2. Loop

3. If OPEN is empty, return failure

4. Node = Remove-First(OPEN)

5. If Node is a Goal

6. Return the path from initial to Node

7. Else

8. Generate all successors of Node

9. For each successor:

10. Calculate f = g + h

11. Add successor to OPEN according to its f value

END Loop

Solution for the graph: check answer in previous example of A*.

Solve 8 puzzle problem for all