Você pode ter /usr/local/bin na $PATH da raiz
mas apenas fazendo sudo não lhe dá o perfil do root onde PATH é setado
você vai conseguir depois de logar como root com
su -
ou
sudo -i
Eles te dão um shell de root.
Se você quiser ficar em uma linha, tente usar
sudo su -c 'my_prog'
se isso não funcionar, aplique-o com -l
sudo su -l -c 'my_prog'