Overview of Trees

This lesson is a quick overview of trees, their types, and some important formulas to compute the height and number of nodes in a tree.

Binary Trees

Definition: A tree having a max. of two children at each internal node

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.