  Continuing the recent trend, in this article we design several
space-efficient algorithms for two well-known graph search methods. Both these
search methods share the same name {\it breadth-depth search} (henceforth {\sf
BDS}), although they work entirely in different fashion. The classical
implementation for these graph search methods takes $O(m+n)$ time and $O(n \lg
n)$ bits of space in the standard word RAM model (with word size being
$\Theta(\lg n)$ bits), where $m$ and $n$ denotes the number of edges and
vertices of the input graph respectively. Our goal here is to beat the space
bound of the classical implementations, and design $o(n \lg n)$ space
algorithms for these search methods by paying little to no penalty in the
running time. Note that our space bounds (i.e., with $o(n \lg n)$ bits of
space) do not even allow us to explicitly store the required information to
implement the classical algorithms, yet our algorithms visits and reports all
the vertices of the input graph in correct order.
