1. A search tree can be represented in LISP as follows: (a) if the search tree contains a single leaf node L, it can be represented by atom L (b) if the search tree has more than one node and is rooted at N, then it can be represented by a list (S1 S2... Sk) where Si represents the ith subtree of N. Consider for example the following search trees, whose LISP representations are shown later. 0 /\ OTRO 0 LE /*/*/* /\ OF Io /\ /\ HT i /1 o C To E AO /\ | A o D | B /I\ H R E /\ o B /\ Co OD I E Write a single LISP function, called BFS. It takes a single argument FRINGE that represents a list of search trees, and returns a top-level list of leaf nodes, in the order they are visited by left-to-right breadth-first search. The inital call to BFS passes a FRINGE list with a single element: the root of the search tree. Test your program on at least these inputs: > (BFS (ROOT)) (ROOT) 1 > (BFS '((((LE) F) T))) (T F L E) > (BFS '((R (I (G (H T}}}}}} (RIGHT) > (BFS '(((A (B)) C (D}}}} (C A D B) > (BFS '((T (HR E) E))) (TEHRE) > (BFS ((A (CC ((E) D)) B}}}} 3 (A B C D E) 1 1. A search tree can be represented in LISP as follows: (a) if the search tree contains a single leaf node L, it can be represented by atom L (b) if the search tree has more than one node and is rooted at N, then it can be represented by a list (S1 S2... Sk) where Si represents the ith subtree of N. Consider for example the following search trees, whose LISP representations are shown later. 0 /\ OTRO 0 LE /*/*/* /\ OF Io /\ /\ HT i /1 o C To E AO /\ | A o D | B /I\ H R E /\ o B /\ Co OD I E Write a single LISP function, called BFS. It takes a single argument FRINGE that represents a list of search trees, and returns a top-level list of leaf nodes, in the order they are visited by left-to-right breadth-first search. The inital call to BFS passes a FRINGE list with a single element: the root of the search tree. Test your program on at least these inputs: > (BFS (ROOT)) (ROOT) 1 > (BFS '((((LE) F) T))) (T F L E) > (BFS '((R (I (G (H T}}}}}} (RIGHT) > (BFS '(((A (B)) C (D}}}} (C A D B) > (BFS '((T (HR E) E))) (TEHRE) > (BFS ((A (CC ((E) D)) B}}}} 3 (A B C D E) 1