K-ary tree

In graph theory, a k-ary tree is a rooted tree in which each node has no more than k children. It is also sometimes known as a k-way tree, an N-ary tree, or an M-ary tree. A binary tree is the special case where k=2.

Note: A tree containing only one node is taken to be of height 0 for this formula to be applicable.

Note: The formula is not applicable for a 2-ary tree with height 0, as the ceiling operator approximates and simplifies the true formula, which can be described as

k-ary trees can also be stored in breadth-first order as an implicit data structure in arrays, and if the tree is a complete k-ary tree, this method wastes no space. In this compact arrangement, if a node has an index i, its c-th child in range [1..k] is found at index ${\displaystyle k\cdot i+c}$, while its parent (if any) is found at index ${\displaystyle \left\lfloor {\frac {i-1}{k}}\right\rfloor }$ (assuming the root has index zero, meaning a 0-based array). This method benefits from more compact storage and better locality of reference, particularly during a preorder traversal.

...
Wikipedia