  We present a tree structure algorithm for optimal control problems with state
constraints. We prove a convergence result for a discrete time approximation of
the value function based on a novel formulation of the constrained problem.
Then the Dynamic Programming approach is developed by a discretization in time
leading to a tree structure in space derived by the controlled dynamics, in
this construction the state constraints are taken into account to cut several
branches of the tree. Moreover, an additional pruning allows for the reduction
of the tree complexity as for the case without state constraints. Since the
method does not use an a priori space grid, no interpolation is needed for the
reconstruction of the value function and the accuracy essentially relies on the
time step $h$. These features permit a reduction in CPU time and in memory
allocations. The synthesis of optimal feedback controls is based on the values
on the tree and an interpolation on the values obtained on the tree will be
necessary if a different discretization in the control space is adopted, e.g.
to improve the accuracy of the method in the reconstruction of the optimal
trajectories. Several examples show how this algorithm can be applied to
problems in low dimension and compare it to a classical DP method on a grid.
