What are Trees ? - data structure tutorial

If you have not seen my previous posts on arrays , linked lists , queues and stacks then please refer to them first and then read about What are Trees ? - data structure tutorial.
Links:

• Arrays 
• Linked Lists
• Doubly Linked Lists
• Circular Linked Lists
• Queues
• Circular Queues
• Stacks

Tree is a non-Linear Data Structure which contain many nodes where one node is the root of the tree and other nodes are children of the root node.
In general, a node can have any number of children it can have only one parent.
Have a look at the picture below:

In the above picture,
A is the root node having B and C as its child.
B is the parent of D E and F.
C is the parent of G.

Basic Tree Terminology

• Root : Root is a node which does not have a parent. e.g: int he above picture A is the root node.
• Parent Node : Immediate Predecessor of a node. e.g: in the above picture A,B,C,E are parent nodes.
• Child Node : Immediate Successor of a node. e.g: in the above picture B and C are child of A.
• Siblings : Nodes which have same parent. e.g: in the above picture B and C are siblings because they have same parent A.
• Height of Tree : Height of  tree represents the height of its root node (calculated from bottom to top).
• Depth of Tree : Depth of tree is same as Height of Tree however it is calculated from top to      bottom).

         

• Height of Node : It is the Height from given node to the last possible leaf node.
• Depth of Node : Depth of a node is calculated from traversal from root to a given node. 

Binary Trees

A Tree whose nodes have at-most 2 children is called a Binary Tree. We name the nodes of a bianary tree from left to right.

Types of Binary Trees

Full Binary Tree 

1.      A full binary tree has 0 or 2 children. 
2.      In full Binary tree number of leaf nodes are calculated by : L=I+1 (L =number of leaf nodes       ,  I =Number of internal nodes).

Complete Binary Tree

1. If you can fill an array (size of array is no of nodes in tree) by extracting values from tree in left to right fashion such that no index location in array is left empty ,then it is known as a Complete Binary tree. 

Perfect Binary Tree

1. A tree in which every internal node has 2 children and all leaves are at at same level.
2. A perfect Binary tree of height 'h' has 2^h-1 nodes.

Balanced Binary Tree

A tree is called a balanced binary tree if :

• The left and right sub-tree's height differ by at most one.
• The left sub-tree is balanced .
• the right sub-tree is balanced.

Degenarate Tree

A tree in which each parent node has only one child node.

Advantages of trees

1. Trees can be used to represent structural relationship in the data.
2. Trees provide an efficient insertion and searching mechanism.
3. Trees are very flexible and they allow to move sub-trees around with minimum effort.

This was all about What are Trees ? - data structure tutorial.

** In the next post we will implement a tree data stucture in c++.