Overview of Trees

A quick overview of trees, its types, and some important formulas to compute height and number of nodes in a tree.

Binary Trees

Definition: A tree where each vertex has two children at most.

Types: Perfect, Full, Complete, Skewed

Total number of nodes: 2(h+1)12^{(h+1)}-1

Total number of leaf nodes: 2hor(n+1)22^{h} or \frac{(n+1)}{2}

Height: log2(n+1)1log_{2}(n+1)-1

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.