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 :


Tree Edges

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  


Length of a path

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 .      


Comments (1)

  1. Pingback: Trees - Simple Operations and Traversal. - The code rider

Leave a comment

Your email address will not be published. Required fields are marked *