Trees – definitions with pictures

Trees – definitions with pictures

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

 

Tree
Tree

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 :

edge
Tree Edges

Leaves: nodes with no children

.  

Siblings: Nodes with the same root.  

siblings
Siblings

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  

path
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

depth
Depth

 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.  

height
Height

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 .      

Facebooktwittergoogle_pluslinkedinFacebooktwittergoogle_pluslinkedin

1 thought on “Trees – definitions with pictures

Leave a Comment