M-ary tree

In graph theory, an m-ary tree (for nonnegative integers m) (also known as n-ary, k-ary or k-way 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 the special case where m = 2, and a ternary tree is another case with m = 3 that limits its children to three. A full m-ary tree is an m-ary tree where within each level every node has 0 or m children. A complete m-ary tree (or, less commonly, a perfect m-ary tree) is a full m-ary tree in which all leaf nodes are at the same depth. For an m-ary tree with height h, the upper bound for the maximum number of leaves is . The height h of an m-ary tree does not include the root node, with a tree containing only a root node having a height of 0. The height of a tree is equal to the maximum depth D of any node in the tree. The total number of nodes in a perfect m-ary tree is , while the height h is By the definition of Big-Ω, the maximum depth The height of a complete m-ary tree with n nodes is . The total number of possible m-ary tree with n nodes is (which is a Catalan number). tree traversal 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 nodes would constitute the left subtree and 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.