Tree Data Structure Tutorial and application

A tree is a Data Structure composed of nodes, where each node is a data structure consisting of value, together with a list of references to the children

Properties of the tree data structure:

1. Each tree has a root node.
2. If a tree has n nodes, then it will have (n-1) edges only.
3. A node with degree 0(or no children) is called a leaf node.
4. A m-ary tree can have at most m children ( maximum degree m). Ex: 2-ary or Binary Tree can have at most 2 children only.
5. A path is the length of edges between source node to other destination nodes.
6. The height of a tree represents the number of edges on the longest path between the root node and a leaf. The height of leaf nodes is always 0.
7. The level of a tree is always height + 1.
8. Max no. of leaf nodes L= n(m-1) + 1 .  Here m represents m-ary tree(m=2 for a binary tree, m=3 for ternary tree and so on), and n is the number of internal nodes with degree m. 

Example

Following is a Ternary (3-ary) Tree

The maximum degree of a node is 3.(Node 7 has max degree 3).

The height of the tree is 3.(Following are the path with maximum path length so will count them towards height 2->7->6->5 or 2->7->6->11 or 2->5->9->1).

2(marked red) is the root node with height 3.  2, 10, 5, 11, 4 are the leaf nodes with height 0.

Important terminologies related to Tree Data Structure

Node: A node is a structure that may contain a value.

Root: The top node in a tree.

Child: A node directly connected to another node when moving away from the root, an immediate descendant.

Parent: The converse notion of a child, an immediate ancestor.

Siblings: A group of nodes with the same parent.

Ancestor: A node reachable by repeated proceeding from child to parent.

Leaf node: A node with no children.

Internal node: A node with at least one child.

Degree: For a given node, its number of children. A leaf is necessarily degree zero. The degree of a tree is the degree of its root.

Edge: The connection between one node and another

Sub Tree: A tree T is a tree consisting of a node in T and all of its descendants in T.

Application of Tree Data Structure

1. Store hierarchical data, like folder structure, organization structure, XML/HTML data
2. Heap is a tree data structure that is implemented using arrays and used to implement priority queues.
3. Trie Used to implement dictionaries with prefix lookup.
4. Spanning Trees and shortest-path trees are used in routers and bridges respectively in computer networks
5. B-Tree and B+ Tree They are used to implement indexing in databases.
6. Binary Search Tree is a tree that allows fast search, insert, delete on sorted data. It also allows finding the closest item
7. Representing sorted lists of data.
8. Creating Binay & Binary Search Tree.