. Let T be a rooted tree such that all the leaves have the same depth d, and all
ID: 3701976 • Letter: #
Question
. 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 ?. Consider 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
Let us see and analyse both the algorithms
In DFS, stack is used for the purpose of backtracking. DFS algorithm pushes the node intothe stack untill reaches at a certain point where no unvisited node can be pushed into the stack. Here it starts popping the nodes out.
In th problem provided to us, we have a tree having depth of each node as d and each internal node has exactly b children. Since we are performing DFS starting from the r, DFS will first push r into the stack, and then one f it's children, it will the perform similar job with the children of the pushed node. When it will reach the child node, not having any children, there will be no more vertices to push, so at that time, it will pop the elemnt out of the stack. It will be the point at which the size of the stack is maximum.
Now, if we are consideing the depth of root as 0, maximum size of stack is d+1 and if depth of r is 1, max size is d.
So, the maximum size of the stack in the given case is theta(d).
Now consider the BFS algorithm. BFS does not maintain a stack, it maintains a queue instead. At the very beginning, BFS enqueues the starting vertex into the queue. It the dequeues the queue and enqueue all it's children into the queue an continues untill the queue is empty.
In the problem give, we will apply BFS starting from the r. It will first enqueue r into the queue. Then it will dequque r and push all it's children into the queue. Similarly it will continue to dequeue and enque untill the queue is empty. One thing to observe here is, nodes are bieng pushed in level order. Each time the node at same levels are dequeued, node at next level are inserted into the queue. The point where no more nodes will be inserted into the queue is the point BFS will start dequeuing the nodes from the very last level. This would be the point of maximum queue size. The maximum number of elements in the queue will be the number of nodes at the last level i.e no of leaf nodes.
If depth of r is 0, then number of leaf nodes = 2d, and if depth of r is 1, nodes = 2d-1. So, we can say the in out problem, the maximum size of BFS queue is of the order theta(2d)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.