This article depicts fundamental definitions of trees. It is an introduction to a series of articles dedicated to trees and their definitions in a simple and understood approach. Some people, like me, understand better with picture, they tend to draw a lot when explaining to others or themselves. Also, they tend to do a lot of hand motions when explaining something. The following summarized definitions are fundamental to understand trees.
A Tree is a collection of nodes
One is called root, and zero or more nonempty children.
Each child or group of children can be considered a tree or a sub-tree of the main tree, thus each child of the main tree can be seen as a root.
A link between a root and its child is called edge If a tree has N nodes then it has N-1 edges, the red numbers on the images show edges nodes :
Leaves: nodes with no children
Siblings: Nodes with the same root.
A path from node n 1 to n k is defined as a sequence of nodes n 1 , n 2 , . . . , n k such that n (i) is the parent of n (i+1) for 1 ≤ i < k The length of this path is the number of edges on the path, namely k − 1
The depth of n i is the length of the unique path from the root to n i . Thus, the root is at depth 0
The height of n i is the length of the longest path from n i to a leaf. The height of a tree is equal to the height of the root.
If there is a path from n 1 to n 2 , then n 1 is an ancestor of n 2 and n 2 is a descendant of n 1 . If n 1 = n 2 , then n 1 is a proper ancestor of n 2 and n 2 is a proper descendant of n 1 .