In graph theory, an m-ary tree (for nonnegative integers m) (also known as n-ary, k-ary, k-way or generic tree) is an arborescence (or, for some authors, an ordered tree) in which each node has no more than m children. A binary tree is an important case where m = 2; similarly, a ternary tree is one where m = 3.

$${\displaystyle {\begin{aligned}&{\frac {m^{h+1}-1}{m-1}}\geq N>{\frac {m^{h}-1}{m-1}}\\[8pt]&m^{h+1}\geq (m-1)\cdot N+1>m^{h}\\[8pt]&h+1\geq \log _{m}\left((m-1)\cdot N+1\right)>h\\[8pt]&h\geq \left\lceil \log _{m}((m-1)\cdot N+1)-1\right\rceil .\end{aligned}}}$$ By the definition of Big-Ω, the maximum depth $${\displaystyle D=h\geq \left\lceil \log _{m}((m-1)\cdot N+1)-1\right\rceil =O(\log _{m}n)=O(\log n/\log m).}$$

Traversing a m-ary tree is very similar to traversing a binary tree. The pre-order traversal goes to parent, left subtree and the right subtree, and for traversing post-order it goes by left subtree, right subtree, and parent node. For traversing in-order, since there are more than two children per node for m > 2, one must define the notion of left and right subtrees. One common method to establish left/right subtrees is to divide the list of children nodes into two groups. By defining an order on the m children of a node, the first ${\textstyle \{1,\dots ,\lfloor {\frac {m}{2}}\rfloor \}}$ nodes would constitute the left subtree and ${\textstyle \{\lceil {\frac {m}{2}}\rceil ,\dots ,m\}}$ nodes would constitute the right subtree.

Using an array for representing a m-ary tree is inefficient, because most of the nodes in practical applications contain less than m children. As a result, this fact leads to a sparse array with large unused space in the memory. Converting an arbitrary m-ary tree to a binary tree would only increase the height of the tree by a constant factor and would not affect the overall worst-case time complexity. In other words, ${\textstyle O(\log _{m}n)\equiv O(\log _{2}n)}$ since ${\textstyle \log _{2}m\cdot \log _{m}n={\frac {\log m}{\log 2}}\cdot {\frac {\log n}{\log m}}=\log _{2}n}$.

First, we link all the immediate children nodes of a given parent node together in order to form a link list. Then, we keep the link from the parent to the first (i.e., the leftmost) child and remove all the other links to the rest of the children. We repeat this process for all the children (if they have any children) until we have processed all the internal nodes and rotate the tree by 45 degrees clockwise. The tree obtained is the desired binary tree obtained from the given m-ary tree.

m-ary trees can also be stored in breadth-first order as an implicit data structure in arrays, and if the tree is a complete m-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,…,m} is found at index ${\displaystyle m\cdot i+c}$, while its parent (if any) is found at index ${\textstyle \left\lfloor {\frac {i-1}{m}}\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. The space complexity of this method is ${\displaystyle O(m^{n})}$.

Each node would have an internal array for storing pointers to each of its ${\displaystyle m}$ children:

Compared to array-based implementation, this implementation method has superior space complexity of ${\displaystyle O(m\cdot n)}$.