Introduction to tree and tree terminology

Tree: A tree is a data structure similar to  a linked list list but instead of each node pointing simply to to the next node in a linear fashion, each node points to a number of nodes.

Tree is a example of non-linear data structures. A tree structure is a way of representing the hierarchical nature of a structure in a graphical form.

The graph theoretic definition of tree is " It is a finite set of one or more data items such that 

1. There is a special data item called the root of the tree.

2. And its remaining data items are partitioned into number of multiple exclusive subsets, each of which itself a tree and they are called sub trees.

 Tree Terminology

1. ROOT:- It is a specially designated item in a tree. It is the first in the hierarchical arrangement of data items. In the above tree, "A" is the root item.

2. NODE:- Each data item in a tree is called node. It is the basic structure in a tree. It specifies the data information and links to other data item. There are 10 nodes in the above tree.

3. LEAF NODE:- A node with no children is called a leaf node, which is not a leaf is called internal node.

4. PATH:- In a tree data structure, the sequence of nodes and edges from one node to another node is called as PATH between that two nodes. Length of a path is total number of nodes in this path.

              Example: A-D-G-J

5.SIBLINGS:-  The children of the same parent are called siblings.

          Example: B and E are siblings 

6. ANCESTOR AND DESCENDANT:- If there is a path between A and B, then A is called an ancestor of B and B is called a descendant of A.

7. SUB TREE:- Any node of a tree, with all of its descendants is a sub tree.

8. LEVEL:- The level of the node refers to its distance from the root. The root of the tree has level  zero. The maximum number of nodes at any level is 2 power n.

9. HEIGHT:- The maximum level in a tree determines its height. The height of a node in a tree is the length of a longest path from the node to a leaf. The term depth is also used to denote height of the tree.

10. DEPTH:- The depth of a node is the number of nodes is the number of nodes along the path from the root to that node.