What is tree density?

Tree density is a characteristic that shows how "filled" a tree is with nodes relative to the maximum possible for its height.

---

#Formally

If a tree's height is h, then the maximum number of nodes (in an ideal perfect tree) equals: [ N_{max} = 2^{h+1} - 1 ]

Density (D) is defined as: [ D = \frac{N_{actual}}{N_{max}} ] where

• ( N_{actual} ) is the actual number of nodes in the tree,
• ( N_{max} ) is the maximum possible at that height.

---

#Example

A tree has height 3 and contains 10 nodes. The maximum at h = 3 → ( 2^{4} - 1 = 15 ). [ D = 10 / 15 = 0.67 ] That is, the tree is 67% filled.

---

#Interpretation

• The higher the density, the better balanced the tree is and the closer it is to perfect.
• Low density indicates sparseness: a lot of "empty space", long branches, lower efficiency.

---

#Summary

Tree density shows how efficiently a tree is filled with nodes for its height. It is a measure of the structure's "compactness": the closer to 1, the more balanced and efficient the tree.