A binary tree is a tree in which every node has at most two children, distinguished as left and right, and this degree constraint yields a taxonomy of structural subtypes — strict/proper, complete, perfect, and balanced — each defined by conditions on how levels are filled and how sub-tree heights may differ. The level/depth/height metrics that follow from the constraint are quantitative: at most 2^i nodes occupy level i, a perfect tree of height h holds 2^(h+1) − 1 nodes, and inverting that relation gives height = log2(n+1) − 1, with floor(log2 n) for complete trees. Within data structures, these properties matter because the time cost of search, insertion, and deletion on tree-based structures is proportional to height, so height bounds of O(log n) versus O(n) separate dense trees from degenerate list-like ones, motivating the balance invariant that later self-balancing structures enforce.
A binary tree is a tree in which every node has at most two children, distinguished as left and right, and this degree constraint yields a taxonomy of structural subtypes — strict/proper, complete, p…