In computer science, a ternary tree is a tree data structure in which each node has at most three child nodes, usually distinguished as "left", “mid” 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 the "root" node (the ancestor of all nodes), if it exists. Any node in the data structure can be reached by starting at root node and repeatedly following references to either the left, mid or right child.

Ternary trees are used to implement Ternary search trees and Ternary heaps.

– Let ${\displaystyle h}$ be height of a ternary tree.

– Let ${\displaystyle M(h)}$ be the maximum number of nodes in a ternary tree of height ${\displaystyle h}$

– ${\displaystyle M(h)=1+3+9+\cdots +3^{h}=\sum _{i=0}^{h}3^{i}={\frac {3^{h+1}-1}{2}}}$

– Every tree of height h has at most ${\displaystyle {\frac {3^{h+1}-1}{2}}}$ nodes.

Nodes can be inserted into ternary trees in between three other nodes or added after an external node. In Ternary trees, a node that is inserted is specified as to which child it is.

Say that the external node being added onto is node A. To add a new node after node A, A assigns the new node as one of its children and the new node assigns node A as its parent.