What is a Tree Data Structure ? | Introduction(with diagram) | Important Tree Terms & Properties

What is a Tree Data Structure ?

A tree is a non linear data structure that simulates a hierarchical tree structure with a root value and sub trees of children with parent node, represented as set of linked nodes.

Real world example of hierarchical tree –

Tree terms –

1. Root – Root is a special node in a tree. The entire tree is referenced through it. It does not have a parent.
2. Parent Node – Parent node is an immediate predecessor of a node.
3. Child Node – All immediate successors of a node are its children.
4. Siblings – Nodes with the same parent are called Siblings.
5. Leaf – Last node in the tree. There is no node after this node.
6. Edge – Edge is a connection between one node to another. It is a line between two nodes or a node and a leaf.
7. Path – Path is a number of successive edges from source node to destination node.

Tree terms / properties –

1. Tree can be termed as a RECURSIVE data structure.
2. In a valid tree for N Nodes we have N-1 Edges/Links
3. Depth of Node – Depth of a node represents the number of edges from the tree’s root node to the node.
4. Height of Node – Height of a node is the number of edges on the longest path between that node & a leaf.
5. Height of Tree – Height of tree represents the height of its root node.

Logical Diagram of Tree Data Structure –

Types of Trees –

• General Tree
• Binary Tree
• Binary Search Tree
• AVL Tree
• Spanning Tree
• B-Tree
• B+ Tree
• Heap

Applications of Tree Data Structure –

• Store hierarchical data, like folder structure, organization structure data.
• Binary Search Tree is a tree that allows fast search, insert, delete on a sorted data.
• Heap is a tree data structure which is implemented using arrays and used to implement priority queues.
• B-Tree and B+ Tree are used to implement indexing in databases.
• Used to store router-tables in routers.
• Used by compilers to build syntax trees.
• Used to implement expression parsers and expression solvers.

YouTube video tutorial –

In further tutorial posts we will study about the different types of Tree Data Structures in detail.