Tree – Introduction, Terminologies and Explanation

A tree is a hierarchical data structure, unlike array and linked list(which are known as a linear data structure).

Saying hierarchy means nodes(or vertices) are ordered in top to down order, i.e. topmost node is referred as Root node.
For example in image below-

• 8 is the root node.
• Node 5 and 10 are said to be children of node 8( immediate parent).
• Node 5 and 10 are the siblings to each other.

Trees and Graphs – Trees can also be generalized as a graph which is acyclic and connected provided any two vertices are connected only through one path.

A tree, with each node having at most 2 children is a Binary Tree.
A tree, with each node having at most 3 children is a Ternary Tree.
A tree, with each node having at most n children is an n-ary Tree.

Note:-
Although there can be an n-ary tree, but in practice, binary trees are more widely used. Further, various modifications of binary trees are also available such as Binary search tree, AVL Tree, Red-Black tree etc.

Advantages of using Tree:

• Widely used operation searching is better optimized with tree data structure. Like balanced binary search tree always takes O(logn) for searching.
• Insertion to a tree is faster than Linked list and slower than the arrays. Interestingly, a binary tree is also implemented using array referred as Heap.
• In case of deletion, it is like a linked list. Deletion is faster against an array.

Necessary conditions for a tree:

• It should not contain any cycle.
• A node should not contain self-loop.
• A child will have only one parent.
• Any two nodes in a tree are connected through only one possible path.

Terminologies:

1. Root node – The topmost node of a tree,
2. Leaf node – Node having no children, <B, I, K, F, G, H>
3. Internal/parent node – all node except leaf node <C, D, E, J>
4. Degree of node X– the number of nodes in neighbor of X or number of subtrees of node X
   e.g. degree(E) = 3 {C, I, J}; deg(B) = 1; deg(J) = 2
5. Edge – Connectivity between two node
6. Path – Sequence of nodes connected one after other through edges.
   e.g. A-D-G, A-C-E-I
7. Height of a node – The longest path from the node X to the reachable leaf node.
   e.g. height(C) = 3 {C-E-J-K}
8. Height of tree – Height of root node is referred as the height of a tree i.e. the maximum no of edges in the greatest path from root node to the leaf node.
   e.g. height of the given tree is 4
9. Level of tree – Level of a tree is the number of nodes from the node to root.
   e.g. level of root A is 1,
   level of node B, C, D is 2,
   level of node E, F, G, H is 3
10. Descendant and Ancestor – As name justified, Descendant of a node is its children and grand children. Similarly, ancestor of a node is its parent and grand parents.

Implementation:

Almost every languages already have the in-built library for trees and it’s multiple implementations as it has very vast applications and is used almost everywhere. In C, it’s implemented using structure. Following is the declaration of a node of a binary tree, left and right pointer represent left subtree and right subtree respectively whereas the data holds the value of the current node.

struct binaryTree{
   int data;
   struct binaryTree *left;  // pointing left subtree
   struct binaryTree *right; // pointing right subtree
   };

Applications of Trees :-

1. Router algorithm
2. Social networking based application
3. File system, Directory implementation
4. Maps typically uses tree data structure
5. In games especially, when the requirement is multi-stage decision-making.

Knowledge is most useful when liberated and shared. Share this to motivate us to keep writing such online tutorials for free and do comment if anything is missing or wrong or you need any kind of help.
Keep Learning… Happy Learning.. 🙂

Recommended -