The global surge of connected devices and multimedia services necessitates increased capacity and coverage of communication networks. One approach to address the unprecedented rise in capacity and coverage requirement is deploying several small cells to create ultra-dense networks. This, however, exacerbates problems with energy consumption and network management due to the density and unplanned nature of the deployment. This review discusses various approaches to solving energy efficiency problems in ultra-dense networks, ranging from deployment to optimisation. Based on the review, we propose a taxonomy, summarise key findings, and discuss operational and implementation details of past research contributions. In particular, we focus on popular approaches such as machine learning, game theory, stochastic and heuristic techniques in the ultra-dense network from an energy perspective due to their promise in addressing the issue in future networks. Furthermore, we identify several challenges for improving energy efficiency in an ultra-dense network. Finally, future research directions are outlined for improving energy efficiency in ultra-dense networks in 5G and beyond 5G networks.