**Tree Data Structure** is a Non-Linear Data Structure. Tree in the data structure is a set of nodes which are connected to each other in a hierarchical fashion.

## What is tree data structure?

**Tree in data structure definition:** Tree is a hierarchical data structure which stores data in hierarchy form.

**Tree** is abstract data type containing the set of one or more data nodes where one node is designated as the root of the tree while the remaining nodes are called as the children of the root.

The tree is a finite set of nodes with one specially designed node called root and remaining nodes are partitioned into n >= 0 disjoint sets T1 to Tn where each of those set is the tree.

T1 to Tn is called as a subtree of root.

**Tree Data Structure** is the most powerful and advanced data structure.

### Tree example

In this example A,B,C,D,E,F,G,H are nodes and A is a special node called root.

### Tree terminology

**1. Node:** It is an item of information along with edges called a node.

In the above example, there are 8 nodes.

**2. Leaf node:** Leaf node is a terminal of a tree, it does not have any node connected to it.

In the above example F, H, G, D are the leaf nodes and remaining nodes are called non-leaf node.

**3. Degree of node:** The number of the subtree of the node is called a degree of a node.

Example:- degree of A = 3

Degree of B = 2

**4. Degree of a tree:** Is the maximum number of nodes.

Example Degree of tree = 3

**5. Parent node:** Is a node having other node connected to it. All that connected nodes are called a child node of that node.

Example

A is a parent node of B, C, D

C is a parent node of G

**6. Sibling:** Children of the same parent are called siblings

Example:- B, C, D are siblings

**7. Descendants:** Descendants of the nodes are all those nodes which are reachable from that node.

Example:- descendants of B is E, F, H

**8. Ancestors:** Ancestors of the node are all the nodes along the path from the root to that node.

Example:- ancestors of E are B and A

**9. Levels of node:** This indicates the position of the node in a hierarchy

Formula level of any node = level of its parents + 1

The level of the root is always zero

Example :

**10. Height or depth of tree:** The maximum level of any node is called as depth or height of the tree.

Example:- height of the above tree is 3

**11. Forest:** It is a set of n >= 0 disjoint trees that are if we remove the root we get the forest trees.

Example :

If we remove node A from above trre then it makes following disjoint trees which are called as forest.

### Types of tree in data structure

**1. Ternary tree:** Every node has less than or equal to 3 nodes.

Example:-

**2. Binary tree:** Binary tree in which every node has less than or equal to 2 children.

Example:-

**3. Complete binary tree:** Tree in which every node has 0 or 2 children.

**4. Binary search tree:**

In a Binary search tree, every node has the following property.

All nodes in left subtree have a value less than or equal to a parent node.

and nodes in the right subtree have a value greater than or equal to a parent node.