VC dimension of a greedy decision tree vs a optimal decision tree Take the  binary splitting tree, for example, the practical implementation is a greedy splitting procedure.
With some fixed depth ℎ, one can fit an optimal decision tree (by trying every possible split).
The two different training procedures would hopefully result in different trees.
My question is whether the VC dimension of both trees/models are the same?
From my school memory, the VC dimension is independent of learning algorithm, can we treat greedy and optimal decision tree are only different in learning algorithms?
 A: As you have already said, the VC dimension does not depend on the algorithm used: the VC dimension simply characterizes the hypothesis class, i.e. the set of classifiers considered by a learning algorithm. Then, if both algorithms consider the same set of trees, the VC dimension must be the same. In your case, if you impose to CART and to your optimal tree learning algorithm that they learn trees with depth at most h, then the set of trees considered are the same, regardless of the algorithm chosen.
There is a distinction to be made for the VC dimension of the individual returned tree. Indeed, each decision tree class (i.e. the set of functions that can be realized using a fixed tree structure letting the internal nodes and the leaf labeling free) has its own VC dimension. If the two algorithms return different trees, then they likely won't have the same VC dimension, and one can expect that the individual VC dimension of the CART tree will be greater than the other, since it is not optimal. This fact can be leverage in practice, but it is not in CART. For more information on this subject, you might be interested in this paper. (Disclaimer: I am one of the author.)
