O pacote tree
está disponível em Universe . Verifique se você ativou:
Depois é só fazer o habitual
$ sudo apt-get update
$ sudo apt-get install tree
Todos os repositórios do Ubuntu (main, universe, restricted, multiverse) podem ser ativados pelo seguinte comando:
sudo add-apt-repository "deb http://archive.ubuntu.com/ubuntu $(lsb_release -sc) main universe restricted multiverse"