  An NP-hard graph problem may be intractable for general graphs but it could
be efficiently solvable using dynamic programming for graphs with bounded width
(or depth or some other structural parameter). Dynamic programming is a
well-known approach used for finding exact solutions for NP-hard graph problems
based on tree decompositions. It has been shown that there exist algorithms
using linear time in the number of vertices and single exponential time in the
width (depth or other parameters) of a given tree decomposition for many
connectivity problems. Employing dynamic programming on a tree decomposition
usually uses exponential space. In 2010, Lokshtanov and Nederlof introduced an
elegant framework to avoid exponential space by algebraization. Later, F\"urer
and Yu modified the framework in a way that even works when the underlying set
is dynamic, thus applying it to tree decompositions. In this work, we design
space-efficient algorithms to solve the Hamiltonian Cycle and the Traveling
Salesman problems, using polynomial space while the time complexity is only
slightly increased. This might be inevitable since we are reducing the space
usage from an exponential amount (in dynamic programming solution) to
polynomial. We give an algorithm to solve Hamiltonian cycle in time
$\mathcal{O}((4w)^d\, nM(n\log{n}))$ using $\mathcal{O}(dn\log{n})$ space,
where $M(r)$ is the time complexity to multiply two integers, each of which
being represented by at most $r$ bits. Then, we solve the more general
Traveling Salesman problem in time $\mathcal{O}((4w)^d poly(n))$ using space
$\mathcal{O}(\mathcal{W}dn\log{n})$, where $w$ and $d$ are the width and the
depth of the given tree decomposition and $\mathcal{W}$ is the sum of weights.
Furthermore, this algorithm counts the number of Hamiltonian Cycles.
