The gemara says that the only thing that Dovid did wrong in the story with Bassheva and Uria is that he should have formally had Uria judged in Sanhedrin before killing him for rebelling against the king. The implication of the gemara is that even a moreid b'malchus must be judged by the Sanhedrin. Tosafos asks that the gemara in Megilla 14b implies that Dovid had the right to kill Naval for being moreid b'malchus by not providing him the food and supplies that he needed, even without judging him in a formal beis din. Why here does the gemara say that he should have judged Uria in the Sanhedrin? Tosafos answers that a Sanhedrin is required only to determine that the person has the status of a moreid b'malchus, but one doesn't need to follow the formal process of sleeping on the din and the regular scrutiny that a capital case would demand.
The Turei Even (Megilla 14b) asks that based on Tosafos approach, it is still difficult to understand how Dovid was able to kill Uria without following the procedure of Sanhedrin. Apparently, Tosafos considers one who is moreid b'malchus without being declared so by the Sanhedrin to be one who isn't deserving of capital punishment. Therefore, even though Uria was moreid b'malchus, it should have been murder to kill him. How can Dovid have done that?
In Maseches Makos and Baba Kama we find a distinction between penalty payments and compensation. When it comes to compensation the function of the beis din is to determine that the money is owed, but once determined it is owed retroactively. Whereas by penalty payments, the decision of beis din is actually what makes the person obligated to pay. Without Beis Din declaring the k'nas, it is not even owed. Similarly here, the Turei Even explains that the concept of the Sanhedrin determining that Uria was moreid b'malchus was like a monetary compensations, not like a penalty payment. It was merely a determination of the facts, but in truth he had status of moreid b'malchus because of his actions even without the formal declaration of the beis din. Therefore, Dovid failed to follow procedure, but since he knew that Uria was moreid b'malchus, he was considered to have that status even without a psak of the sanhedrin and therefore Dovid did not kill an innocent man.
Perhaps another approach to answer Tosafos question (this is another possible approach, not pshat in Tosafos) is that the function of the Sanhedrin is not to declare the person moreid b'malchus or even to verify that he is a moreid b'malchu. The king can make that decision without the Sanhedrin. However, if he is going to be killed b'yadayim by the Sanhedrin, they are only entitled to kill when they follow a standard process and procedure. Therefore, when it came to Naval who Dovid had to kill b'yadayim, he needed the process of a beis din. But when it came to Uria who Dovid was able to set up to be killed indirectly by putting him on the front lines, he didn't require a Sanhedrin. This approach is really the opposite of Tosafos. The purpose of the Sanhedrin is NOT to declare him a moreid b'malchus, it is necessary to follow the standard procedure of din if they are going to carry out capital punishment.