Tested with sv_SE.UTF-8. The "tree" command doesn't display non-ASCII characters in file names, even though those files I tested with are encoded in valid UTF-8 and display fine in ls and many other commands.
Fixed package is tree-1.2-21, which will show up in rawhide shortly. As a work-around, use -N.