Implement the four algorithms for which there are functions in the Search class.

a. Make sure to read any comments very carefully and follow their directions.

b. Your implementation must display the node being traversed and indicate when the goal is found.

c. Search must stop when the goal is found, when this is in fact the case.

d. The output for the completed version of the program using the two sample test cases provided is shown below.

e. Note that program output must formatted be exactly as shown here. --- Test Case 1 ---

BFS goal: 14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

Goal Found!

DFS

goal: 14

1

2

4

8

5

9

10

14

Goal Found!

Node.Java ------------------------------------------------------------

// This class implements a simple tree node that can be // used by the search algorithms. // // Do NOT make any changes to the code in this class. public class Node { Node left; Node right; int depth; int data;

public Node(Node left, Node right, int data) { this.left = left; this.right = right; this.data = data; }

public Node(int data) { this.data = data; }

public void setDepth(int depth) { this.depth = depth; }

public Node() { left = null; right = null; data = 0; } }

Search.Java -------------------------------------------

import java.util.LinkedList; import java.util.Queue; import java.util.Stack;

public class Search { // Do NOT make any changes to the method name or parameters public static void BFS(Node tree, int goal) { System.out.println("BFS"); System.out.println("goal: " + goal); Implement the algorithm for BREADTH-FIRST-SEARCH } // Do NOT make any changes to the method name or parameters public static void DFS(Node tree, int goal) { System.out.println("DFS"); System.out.println("goal: " + goal); Implement the algorithm for DEPTH-FIRST-SEARCH } // Do NOT make any changes to the method name or parameters public static void DFSLimited(Node tree, int depthLimit, int goal) { System.out.println("DFS Limited"); System.out.println("depth limit: "+ depthLimit); System.out.println("goal: " + goal); //Implement the algorithm for DEPTH-LIMITED-SEARCH } //Do NOT make any changes to the method name or parameters public static void iterativeDFS(Node tree, int goal) { System.out.println("DFS Iterative"); System.out.println("goal: " + goal); //Implement the algorithm for ITERATIVE-DEEPENING-SEARCH } }

Test.Java --------------------------------------------------------

public class Test { public static Node populateNode_Test1() { Node node = new Node(new Node(new Node(new Node(8), null, 4), new Node(new Node(9), new Node(new Node(14), null, 10), 5), 2), new Node(new Node(new Node(11), null, 6), new Node(new Node(12), new Node(13), 7), 3), 1); // 1 // 2 3 // 4 5 6 7 // 8 9 10 11 12 13 // 14 return node; } public static Node populateNode_Test2() { Node node = new Node(new Node(new Node(new Node(8),new Node(9), 4), new Node(new Node(10), new Node(11), 5),2), new Node(new Node(new Node(12), new Node(13), 6), new Node(new Node(14), new Node(15), 7),3),1);

// 1 // 2 3 // 4 5 6 7 // 8 9 10 11 12 13 14 15 return node; } //Do NOT make any changes to the code in this method public static void main(String[] Args) { // Test 1 Node tree = populateNode_Test1(); System.out.println("--- Test Case 1 ---"); Search.BFS(tree, 14); System.out.println(" "); Search.DFS(tree, 14); System.out.println(" "); Search.DFSLimited(tree, 2, 14); System.out.println(" "); Search.iterativeDFS(tree, 14); System.out.println(" "); // Test 2 Node tree2 = populateNode_Test2(); System.out.println("--- Test Case 2 ---"); Search.BFS(tree2, 7); System.out.println(" "); Search.DFS(tree2, 7); System.out.println(" "); Search.DFSLimited(tree2, 2, 7); System.out.println(" "); Search.iterativeDFS(tree2, 7); } }