a) Write a function to generate and store the tree. Students can define a data structure with various attributes such as Tree(1).ID, Tree(1).name, Tree(1).status, Tree(1).parent, Tree(1).children, Tree(1) cost, Tree(1).state Student must input the initial state of the 8-puzzle problem and then find the goal node from this initial node. For example, following is the initial node, 4 5 8 1 7 3 2 6 And the final goal is 1 2 5 8 3 6 4 7 You will make functions check_goal(state) and generate_children(state) b) For a tree, find the goal node by DFS and BFS and record the time and space complexity of the algorithms in a table and discuss the results. c) Avoid loops by using Visited nodes list. Also generate the path from the initial node to the goal node. Submission: (0) Table Working code Lab Assignment 1 a) Write a function to generate and store the tree. Students can define a data structure with various attributes such as Tree).ID, Treef 1). name, Tree(1).status, Treef 1).parent, Tree!).children, Tree).cost, Treol).state One method of entering the tree in the data structure is to store every node manually b) For a tree, find the goal node by DFS and BFS and record the time and space complexity of the algorithms in a table and discuss the results, Time complexity Tic %yourCode timc Elapsed toc Space complexity Maximum length of the fringe variable during execution of the code. Submission: (1) Table (ii) Working code Cheating of report or code is not allowed and were marks will be awarded to the students who copy the code from each other. Example of Tree Depth = 0 D Depth : 1 H Depth = 2 J N Depth = 3 Depth = 4