Note : If you directly copy – paste this solution , you may get any error.
Question 1
Suppose you have a binary tree represented as a Prolog term. Can you write a Prolog program that recursively traverses the tree and returns a list of all the leaf nodes?
% Base case: An empty tree has no leaf nodes. Leaf_nodes(empty, []).
% Case 1: If the tree has only one node, it is a leaf node. Leaf_nodes(tree(Value, empty, empty), [Value]).
% Case 2: If the tree has a left subtree and a right subtree, recursively find the leaf nodes in each subtree.
Leaf_nodes(tree(_, Left, Right), LeafNodes) :- Leaf_nodes(Left, LeftLeaves), Leaf_nodes(Right, RightLeaves), Append(LeftLeaves, RightLeaves, LeafNodes).
Question 2
Suppose you have a directed graph represented as a list of edges, where each edge is a pair of vertices (e.g. [2,3]). Can you write a Prolog program that uses search to find all paths of length N between two given vertices in the graph?
% Base case: If the start and end vertices are the same and the length is 0, return a path with only the start vertex.
Find_paths(_, Start, Start, 0, [[Start]]).
% Recursive case: Find paths of length N between the start and end vertices using
DFS.
Find_paths(Edges, Start, End, N, Paths) :- N > 0,
N1 is N – 1,
Find_paths_helper(Edges, Start, End, N1, [Start], Paths).
% Helper predicate for DFS.
Find_paths_helper(_, Current, Current, 0, Path, [Path]). Find_paths_helper(Edges, Current, End, N, Path, Paths) :-
N > 0,
N1 is N – 1,
Member([Current, Next], Edges),
\+ member(Next, Path), % Avoid revisiting vertices already in the path to prevent cycles
Find_paths_helper(Edges, Next, End, N1, [Next|Path], Paths).
Question 3
Suppose you have a list of 5 integers [1, 2, 3, 4, 5], and you want to generate all possible combinations of 3 elements from this list using Prolog. Write a program that finds all valid combinations by considering all possible options for each element until a valid combination is found.
% Base case: When the combination length is 0, return an empty list. Combinations(_, 0, []).
% Recursive case: Generate all possible combinations by considering all options for each element.
Combinations([X|T], K, [X|Comb]) :- K > 0,
K1 is K – 1,
Combinations(T, K1, Comb).
Combinations([_|T], K, Comb) :- K > 0,
Combinations(T, K, Comb).
If you find anything wrong in this Solution, feel free to reach us in the comment section.
