**Tree in data structure tutorial** is very important concept in data structure.

In this tutorial we are going to see tree in data structure, tree in data structure definition, and tree terminology.

**What is tree in data structure ?**

**Tree in data structure definition : **Tree is 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 tree.

T1 to Tn is called as subtree of root.

**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**

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

In above example there are 8 nodes.

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

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

**Degree of node : **The number of sub tree of the node is called as degree of node.

Example degree of A = 3

Degree of B = 2

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

Example Degree of tree = 3

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

Example

A is a parent node of B, C, D

C is a parent node of G

**Sibling : **Children of the same parent are called as siblings

Example B,C,D are siblings

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

Example descendants of B is E,F, H

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

Example ancestors of E is B and A

**Levels of node : **This indicate the position of node in hierarchy

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

The level of root is always zero

Example :

Level of D = 1

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

Example height of above tree is 3

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

Example :

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

**Tree types data structure**

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

Example

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

Example

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

**Binary search tree :**

In Binary search tree every node has following property

All nodes in left sub tree have value less than or equal to parent node

and nodes in right sub tree have value greater than or equal to parent node

## Leave a Reply