Let:
- $T$ be a rooted tree such that all the leaves have the same depth $d$
- all internal nodes have exactly $k$ children
- $r$ be the root of $T$.
Assume $T$ as a graph, represented 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 non-recursive procedure starting at root $r$, what will be the maximum size of the stack during the computation in $O$ notation?
As an alternative, if we did this recursively, what will be the maximum size of the stack in $O$ notation?
For the first part of the question, I am leaning towards $O(n)$ because of the order of the depth of each of the leaves, but I'm not sure. I'm also completely clueless on the second part.
Any tips would be appreciated!
Best Answer
Recall how depth-first-search algorithm works.
At the beginning the stack contains only the start node and all the nodes are not "discovered".
While the stack is not empty we pop the node from it and push in all it's neighbors. We want to push the neighbors of any given node only once, so we mark already processed nodes: after we pop the node from stack we check if it is marked (aka discovered), if it is - skip it, if it is not - do mark it and push neighbors after that.
Now model the algorithm progress in your case. Push start node, remove it and push in all $k$ children, pop last of them and push in all the $k$ of it's children, and so on until you reach the leaf node.
By that moment there will be exactly $(k-1)*d+1$ nodes in the stack. In $O$ notation it would be $O(k*d)$. May be you want an answer as a function of $n$ and $k$ - in this case just use an equation $n=k^d$, where $n$ is a number of leaf nodes: $O(k*\log_k n)$
Continue the mental simulation of the algorithm and it should become obvious that this is the maximum size of the stack. It will decrease and grow, but never reach that size again.
The recursive version is different in that instead of pushing all the neighbors of some node to stack you recursively call the same function, and this function would use it's own stack to track children of the current node. Instead of a single large stack there is a stack of function calls, each function has it's own smaller stack with nodes. Not a big difference.
Each of these smaller stacks used by the recursively called functions contain neighbors of some node, so it's size can't be larger than $k$. I guess the answer to a second question is $O(k)$.