Are decision trees sparse or dense?

Question

Are decision trees or game trees such as these sparse or dense?

This wiki page goes on about calling trees "tight". Is that dense or a third type?

Also if the graph is sparse, must its matrix representation also be sparse and vice versa?

I'm really lost, please help

Answer 1

Decision trees are sparse.

I figured it out empirically. With my limited knowledge of math, I know that dense graphs have most nodes connected and spares have very few. I made a realistic decision tree of 16 nodes, as dense as I could make it up. Then I put it in a matrix. In a 16x16 matrix (256 cells) there were only 15 connections (5.9%). Would be 30 connections (11.8%) if I made it symmetric, which is unnecessary. Very few no doubt.

Answer 2

See this. Since the number of edges in your tree(s) with $n$ nodes is greater than $n$, the trees are in fact dense.