Data structures, amongst other things, are used to store and organize data. Different types of data are more efficiently organized using particular data structures. 

**Trees** are non-linear data structures which are quite often used to represent hierarchical data such as the employee organizational structure in a company.


# Structure of a Tree:

A collection of entities called **nodes** (represented as circles in our diagrams) are linked together with an **edge** to simulate a hierarchical structure. Each node contains data that can be of any type as long as all the nodes contain the same type of data. 


### Components of a Tree:

**Root**: A node with no incoming link to another node, i.e. no parent.

**Child:** A node with an  incoming link from an upper node, i.e. a parent node. A child can only have one parent.

**Parent**: A node with an outgoing link to a lower  node, i.e. a child node. A parent can have multiple children.

**Siblings**: Children nodes with the same parent.

**Leaf:** A node with no outgoing link to a lower node, i.e. no child node. 

**Depth:** The depth of a node, **'x'**, is the number of edges (links) in the path from the **root** node to the node **'x'**. 
In the example on the right, the depth of node **'x'** is **2**.       

**Height:** The height of a node, **'x'**, is the number of edges (links) in the longest path from the node **'x'** to a **leaf** node. 
In the example on the left, the height of node **'x'** is **0** because it is zero edges away from the root node, while the height of the root node is **2**. The height of a tree is equivalent to the height of the node with the maximum height.      

**Subtree:** A subtree is a smaller tree within a larger tree. The root node of a subtree can be any node of the larger tree. In the example on the left, tree *A* is a subtree of tree *B*.    

# Different Types of Trees:

Many different types of trees exist which are optimized for particular use-cases. Each tree type offers its own particular structure. Some commonly used trees include:

* Binary Trees
* [Binary Search Trees](https://www.educative.io/answers/what-is-a-binary-search-tree)
* [AVL Trees](https://www.educative.io/answers/what-is-an-avl)
* Red-Black Trees
* [2-3 Trees](https://www.educative.io/answers/what-is-a-23-tree)
* [2-3-4 Trees](https://www.educative.io/answers/what-is-a-234-tree)

What is a Tree?

Data structures, amongst other things, are used to store and organize data. Different types of data are more efficiently organized using particular data structures. Trees are non-linear data structures which are quite often used to represent hierarchical data such as the employee organizational structure in a company. 

What is a Tree?

Structure of a Tree:

Components of a Tree:

A Sample Tree:

Different Types of Trees: