Should programming assignments be graded based on results from unit tests or based on the similarity to the correct implementation?

Imagine students in a course on algorithms & data structures, which are given homework assignments to implement things like trees, hash sets, sorting algorithms, etc.

Due to the high number of students per semester and limited resources, grading is heavily assisted by automatic unit tests. The TAs will still scan through the code, but if all or most of the test cases fail and there is no simple fix in sight, students will get 0 points on an assignment.

Unfortunately, this can happen very quickly. Consider implementing a balanced tree as an example. If students fail to correctly reference the nodes, insertion, removal and searching, - despite being implemented correctly if seen individually - will not work and can hardly be tested.

As expected, some students do complain about their poor grade and argue that "although they acknowledge that their data structure does not work entirely, they at least implemented various sub-tasks correctly". This may even be correct, but the TAs very often do not have the time to dig deep in the code and grade the internal functions of the students implementation. Especially for more complex data structures, it would also take too much time to fully comprehend and even debug the (erroneous) implementations.

My question is, if it is okay to grade programming assignments based on this external view (does the implementation pass the tests?) or should grading rather be based on an internal view (are the things implemented by the student correct if seen individually?).

One important remark: In this specific scenario, students were not given the unit tests, since they are expected to test their implementation themselves.

Actually, life isn't so simple as to choose one or the other here. Code needs to be well structured andit needs to be correct. Given that students are learning, you can't really expect that they will be perfect on either of these and so you need to take both in to account. A program could, be well designed and built but have some, as yet undiscovered, flaw that prevents it from passing its tests. If the students hack it up to get tests to pass they are going backwards, not forwards.

CS students have a lot to learn. Programming is important, but not the most important thing. But to advance on many of the other goals of the CS curriculum, students need to build good code. Even better, would be the ability to build maintainable code, since many of them will start their careers in programming-heavy jobs. Even if they go to grad school, much of what they do will depend on being able to write good code.

So, in grading, points should be gained or lost depending on both code and correctness. If the code is not correct, then someone needs to make an analysis about why the code is failing. It could be something simple or profound.

In my view if a program can't be understood easily and/or seems to be hacked together, it should receive few points. If a program, on the other hand, passes few tests then it is a much more subtle problem that needs deeper analysis. Don't neglect it.

In the question heading you talk about the "correct implementation". I worry about that. Students should not be graded on similarity to any reference implementation, certainly. There are more than a few ways to write a correct program.