A tree is a non-linear data structure that organizes data in a hierarchical structure and this is a recursive definition. It is a set of one or more nodes, with one node identified as the tree’s root and all remaining nodes partitionable into non-empty sets, each of which is a subtree of the root.

Since it is a non-linear data structure, different tree data structures provide for faster and easier access to the data.

## Tree Terminologies

#### Node

A **node** is a unit of data that contains a key or value as well as pointers to its child nodes.

#### Edge

The connecting link between two nodes is called a **link**.

#### Root

The topmost node in a tree is called the **root node**. This is where the tree is originated from.

#### Parent Node

A **parent node** or ancestor is a node that has a branch from it to another node.

#### Child Node

A **child node** (descendant or successor) is a node that is a descendent of another node.

#### Sibling Nodes

Nodes that have the same parent are called **sibling nodes**.

#### Leaf Node and Internal Node

The node which does not have any child is called a** leaf node** or terminal node. The nodes having at least a child node is called an **internal node**.

#### Level of a Tree

Each step from top to bottom in a tree is referred to as the **level **of a tree.

#### Degree

The total number of children of a node is the **degree** of a node. The number of edges arriving at that node is called the **in-degree** of a node. The number of edges leaving that node is the **out-degree** of a node.

The highest degree of a node among all the nodes in the tree is referred to as the **degree **of the tree.

#### Depth

The total number of edges from the root node to a particular node is called the **depth** of that node.

#### Height

The **height** **of a node** is the total number of edges that lie on the longest path from the node to any leaf node.

The** height of a tree** is the height of the root node.

## Types of Tree

- Binary Tree
- Binary Search Tree
- AVL Tree
- B-Tree
- Expression trees
- Tournament trees

## Applications of Tree

- To search an element in a set quickly, Binary Search Trees(BSTs) are used.
- Heap sort is done by a kind of tree called Heap.
- Tries are modified version of trees used to store routing informations in routers.
- Compiler use a syntax tree to parse program you write.
- Shortest path trees and spanning Trees are used in bridges and routers.