CS uses mathematical proofs. You don't need a computer to execute your code to tell why the BST doesn't work. You can introspect your code and figure out why it works or does not work. If it's correct, CS methodology says you can "prove" that it works (without executing it).
Working with large AI models is like working with an artificial brain. It's as scientific as neuroscience in this sense. You make some hypotheses, tweak some hyperparameters, and get a result, which may or may not invalidate your hypotheses. Nobody knows why. Science is not necessarily about knowing the fundamental "whys" (amateurs think humanity has figured all the "whys" out, but that's a lie). It's about establishing some useful model of how things work.
But it's definitely possible to know why your BST does not work, even without a computer, without empirical testing. That's why CS is not a science.
Psychology is a science. You can make falsifiable statements about the human brain. You will need experiments to build and test theories. It's the same with deep learning.
With computer "science" (and math) it's not the same. You can reason completely about your subjects, i.e. you can determine if something will or will not work just by reasoning, no experiments needed.
For more information on the differences between math and science I recommend reading: https://en.wikipedia.org/wiki/Scientific_method#Relationship...
Given enough computing power, most theories could theoretically by proven or falsified purely through reasoning.