A tree is set of one or more nodes, where:
- There is one designated root node of the tree, .
- The remaining nodes are partitioned into disjoint sets , where each of the sets are also trees. The trees are called subtrees of .
Trees use the same terminology as family trees to describe relationships between nodes. A node can have a parent, a sibling, a grandparent, etc. [1, P. 311].
The number of subtrees of a tree is called its degree. A tree of degree 0 is a leaf [1, P. 308].
A forest is a set of of zero or more disjoint trees. Deleting the root of a tree creates a forest [1, P. 309].
A rooted binary tree can be represented as nodes with pointers
parent points to the parent node,
left points to the left child node and
right points to the right child node [2, P. 246].
is the root of the tree if
Note: future diagrams don’t show NULL pointers explicitly.
A rooted tree node with children (an n-ary tree) can be represented using similar pointers. Instead of a pointer to each child from the parent, each node contains a
left_child pointer to the leftmost child (or
NULL if not), and a
right_child pointer to the right most child (or
NULL if ).
Each node then contains two pointers:
left_sibling points to the previous sibling (
NULL if none exists), and
right_sibling points to its immediate right sibling (
NULL if none exists) [2, P. 246].
-  D. E. Knuth, The Art of Computer Programming, vol. 1. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1998.
-  T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. The MIT Press, 2009.