4. Let T be a rooted tree such that all the leaves have the same depth d, and al
ID: 3709900 • Letter: 4
Question
4. Let T be a rooted tree such that all the leaves have the same depth d, and all the internal nodes have exactly b children, and let r be the root of T. Consider T as a graph, and represent it with adjacency lists, where the edge to the parent of a node follows the edges to the children. If we perform depth-first search on T with a nonrecursive procedure starting at vertex r, what will be the maximum size of the stack during the computation? And what about breadth-first search? Use O or e (20 pts.) notation.Explanation / Answer
Answer :
I) As we know that the stack in depth-first search contains the pointer of all the intermediate nodes until is reach to any of the leaf nodes. After identifying a leaf node, it backtracks and tries to reach the next leaf node before backtracking again. So maximum size of stack required during computation will be the order of its depth. Hence answer is O(d)
II) According to the algorithm, Breadth-first search first traverses all the elements at the same level and then reach out to next level in depth. Now as given in the question and assuming root node at level 0. Number of nodes at each level when each node has exactly b children will be as follows
level 0 -----------------------> 1 node
level 1 -----------------------> b nodes
level 2 ------------------------> b*b = b^2 nodes
level 3--------------------------> b^2*b = b^3 nodes
and so on....
level d -------------------------> b^d nodes;
Hence when bread first will be traversing d-1 level of tree rooted at r then it will need maximum size of queue to store all the leaf node. So, answer is O(b^d) .
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.