a. A full thin binary tree is a binary tree where every non-leaf has exactly two children where at least one of the children is a leaf. Write an algorithm, based on DFS or BFS, that takes as input an undirected graph G, and returns whether or not G is (or can be viewed as) a full thin binary tree. Analyze the time complexity of your algorithm

. b. A bipartite graph is a graph G=(,E) such that the set can be partitioned into two (disjoint) sets 1 and 2 (=12 ) where every edge in the graph is between a node a 1and a node in 2 . A 3-layer complete graph is a graph G=(,E) such that the set can be partitioned into three (disjoint) sets 1 , 2 and 3 ( = 1 2 3 ) where every node in 1 is adjacent to all node in 2 , and every node in 2 is adjacent to every all in 1 and to all nodes 3 , and there are no other adjacencies. Show that a 3-layer complete graph is also a bipartite graph. Then, using a graph traversal technique, write an algorithm that takes as input an undirected graph G, and returns whether or not G 3-layer complete graph; if it is, the algorithm should also return 1 , 2 and 3 . Analyze the time complexity of your algorithm