# 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.

## Types of k-ary trees

• A full k-ary tree is a k-ary tree where within each level every node has either 0 or k children.
• A perfect k-ary tree is a full [1] k-ary tree in which all leaf nodes are at the same depth.[2]
• A complete k-ary tree is a k-ary tree which is maximally space efficient. It must be completely filled on every level (meaning that each level has k children) except for the last level (which can have at most k children). However, if the last level is not complete, then all nodes of the tree must be "as far left as possible". [1]

## Properties of k-ary trees

• For a k-ary tree with height h, the upper bound for the maximum number of leaves is $k^h$.
• The total number of nodes is $\frac{k^{h + 1} - 1}{k - 1}$, while the height h is
$\left\lceil\log_k (k - 1) + \log_k (\mathit{number\_of\_nodes}) - 1\right\rceil.$

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

Note : Formula applicable only for number_of_nodes = number of nodes in *complete* k-ary tree

## References

1. ^ a b "Ordered Trees". Retrieved 19 November 2012.
2. ^ Black, Paul E. (20 April 2011). "perfect k-ary tree". U.S. National Institute of Standards and Technology. Retrieved 10 October 2011.
• Storer, James A. (2001). An Introduction to Data Structures and Algorithms. Birkhäuser Boston. ISBN 3-7643-4253-6.