## Introduction of Tree

• Tree is also known as General Tree.

## Terminology

#### Root:

• Nodes that have no parent is called Root Node.
• They are at the top position in the tree.

#### Parent Node :

• Nodes that are represented at the tail of an arrow is called Parent Node.

#### Child Node :

• Nodes that are represented at the head of an arrow is called Child Node.

#### Internal Node :

• A Node with at least one children in a tree is called Internal nodes.
• All the nodes except leaf nodes in a tree are known as internal nodes.

#### External/Leaf Node :

• A Node with no children in a tree is called External or leaf nodes.

#### Siblings :

• Nodes that are derived from same parent are collectively known as Sibling node or child.

#### Ancestors:

• The node itself, its parent, its parent of parent etc. are considered as ancestors in a tree.

#### Descendent:

• The node itself, its child, its child of child etc. are considered as descendent in a tree.

#### Path:

• The set of edges from a root to a particular node in sequence in a tree is called path of that node.

#### Path Length:

• The total no. of edges used in a path is called the length of the path.

#### Level of tree:

• The longest path length from the root.
• The root is considered as level 0.

#### Level of node:

• The path length from the root to that node is called Level of node in the tree.

#### Depth of tree:

• The depth of a tree is equal to the length of the longest leaf node.

#### Depth of a node:

• The length of the unique path from the root to that node is the depth of a node.
• Number of ancestors of that node is called depth of a node.

#### Height of tree:

• The longest path length from root to a leaf node is called Height of tree.
• The maximum depth of any node in a tree is called height of the tree.
• All leaves are considered as at height 0.
• The height of a tree is equal to the height of the root.

#### Degree of node:

• The maximum number of possible children/child nodes of individual node in the tree is called the degree of that node.

#### Degree of tree:

• The maximum number of possible children/child nodes of a node in the tree is called the degree of tree.

## Definition of Tree

• The tree is a non-linear, non-contiguous, acyclic, and hierarchical data structure in which a huge amount of data is stored in the form of root nodes, parent nodes, and child nodes.
• A tree (upside down) is an abstract model of a hierarchical structure.

## Properties of Tree

• Usually a tree consists of single or multiple nodes with a parent-child relation but it may be empty.
• Each element/node of the tree (except Root – the single top & a special element/node that may have zero or more nodes/subtrees and also without any parent) has a parent and zero or more children elements.
• A tree may be empty or having no nodes i.e. an empty tree is also a tree.
• The number of nodes may be different for each node in the tree.

## Types of Tree

There are following types of tree –

1. Binary Tree
2. Binary Search Tree(BST)
3. AVL Tree
4. Heap
5. B and B+ Tree
6. Red-Black Tree
7. Splay Tree
8. AA Tree
9. 2-3 Tree
10. Huffman Tree

## Use/Application of Tree

• General tree structure is used to store hierarchical data/information such as in folder/directory structures of a hard disk drive.
• In XML parser that uses tree data structure.
• The decision tree concept are used in machine learning algorithm.
• Tree data structure concept is used in DNS structure.
• Normally a database uses tree data structure for indexing.
• The internal architecture of social networking sites use the concept of tree data structure.
Categories: Tree