In this blog post will study what is a tree data structure, types, applications and basic operations on tree ADT.

Definition

A tree is a data structure similar to a linked list but instead of each node pointing to the next node in a linear fashion, each node points to a number of nodes. Tree is an example of a non-linear data structure.

A tree structure is a way of representing the hierarchical nature of a structure in a graphical form. In trees ADT (Abstract Data Type), the order of the elements is not important.

Terminologies

• Root: The root of a tree is the node with no parents. There can be at most one root node in a tree (node A in the above example).
• Edge: An edge refers to the link from parent to child (all links in the figure).
• Leaf Node: A node with no children (E,J,K,H and I).
• Siblings: Children of same parent (B,C,D are siblings of A, and E,F are the siblings of B).
• Ancestor: A node P is said to be the ancestor of node Q if there exists a path from node P to Q. Likewise, node Q is said to be the descendant of node P (B is an ancestor of J).

Properties

• Height of a node: The height of a node is the length of the path from that node to the deepest node (height of G is 1, G - K).
• Depth of a node: The depth of a node is the length of the path from the root to the node (depth of G is 2, A – C – G).
• Height/Depth of a tree: It is the length of the path from the root to the deepest node in the tree (Height/Depth of tree for above example is 4).
• In a tree, if there are N nodes then there will be N-1 edges.

Types

1. General Tree
2. Binary Tree
3. AVL Tree
4. Spanning Tree
5. B-/B+ Tree
6. Skew Tree
7. Heap

In this series, we shall see about binary trees and heap only.

Applications

1. Store hierarchical data like folder structure, organization structure data.
2. Heap is a tree data structure which is implemented using arrays and used to implement priority queues.
3. B- Tree and B+ Tree are used to implement indexing in databases.
4. Used to store router-tables in routers.
5. Used to implement expression parsers and expression solvers.

Basic Operations

1. Inserting an element into a tree.
2. Deleting an element from a tree.
3. Searching for an element.
4. Traversing the tree(BFS/DFS).