type Tree<'a> = Empty | Node of 'a * Tree<'a> * Tree<'a>
But that doesn't mean that C#-style pattern matching (really, Is-patterns and a Type Switch) don't fall under the umbrella of Pattern Matching. You can define tuple patterns that you can match on with the switch statement in C#, which is every bit a form of pattern matching as matching on a particular case of a union type.
I'm afraid that is not the case, because in the current C# version, the compiler does nothing help you determine if you've matched all the possibilities. (it is not exhaustive)
Exhaustiveness is important because it gives warning or an error to help you refactor and modify code without fear of breaking other code. Why engage in all the static typing business if the compiler is not going to help you refactor things?
This is important in the same way that adding a subclass requires exhaustively supplying all the abstract methods (true pattern matching is "dual" to adding a subclass; you use the compiler feedback to direct what actions to take next. you can't do this with the Switch based formulation because you don't get any feedback from the compiler if you missed cases or have refactored other code to add cases (for example, adding/refactoring abstract methods in a base class provides feedback on where to add/update methods in the subclasses)
I agree with you that exhaustiveness is incredibly important, and I really hope that it can be done in C# some day. However, record and union types are also a piece of this puzzle.
I also think language level support for this would be a killer feature, it turns OOP and the requirement to use polymorphism to guarantee strategy-per-type on it's head.