The Basic Algorithm of pseudo-Boolean programming due to Hammer and Rudeanu allows to minimize nonlinear 0-1 functions by recursively eliminating one variable at each iteration. We show it solves in linear time problems whose objective functions are associated with k-trees. Moreover, we propose some shortcuts in boolean manipulations. Computational experiences are discussed.