K-ary tree
Encyclopedia
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.
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 k-ary tree in which all leaf nodes are at the same depth.
For a k-ary tree with height h, the upper bound for the maximum number of leaves is
. The total number of nodes is 
, while the height h is
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a k-ary tree is a rooted tree
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a 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
Binary tree
In computer science, a binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to...
is the special case where k=2.
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 k-ary tree in which all leaf nodes are at the same depth.
For a k-ary tree with height h, the upper bound for the maximum number of leaves is
. The total number of nodes is , while the height h is