A Tree is a non-linear data structure used to store data hierarchically. Unlike arrays or linked lists, data in a tree is not stored in a straight line. Instead, data is arranged like a family tree, where one element is connected to many others. That is why this structure is called a tree.

Why do we need Trees?

Let’s understand with a simple problem: If you store data in an array or list, Searching can become slow, and the data has no clear hierarchy. However, many real-world things are naturally hierarchical, such as the folder structure in a computer and the organizational structure of a company. Trees in data structures are designed exactly for these situations. Trees help us:

1. Organize data clearly
2. Search data faster
3. Represent parent-child relationships
4. Build advanced data structures

Basic Tree Terminology

A tree is made of nodes connected by edges. Here are the important words you must know:

1. Node: A node is a single unit that stores data.
2. Edge: An edge is a connection between two nodes.
3. Root: Top-most node of the tree.
4. Parent: A node that has a child.
5. Child: A node connected below a parent.
6. Leaf Node: A node with no children.
7. Subtree: A smaller tree inside the main tree.
8. Depth: Distance from the root to a node.
9. Height: Distance from the node to the deepest leaf.
10. Degree: Number of children.

Simple Tree Example

        A
      / | \
     B  C  D
       / \
      E   F

• A is the root
• B, C, and D are the children of A
• E and F are the children of C
• B, D, E, F are leaf nodes

Types of Trees in Data Structures

Trees are classified based on how data is stored and connected. Each tree type is designed to solve a specific problem efficiently.

1. General Tree: A node can have any number of children. Used in folder systems
2. Binary Tree: A node can have at most two children, the Left child and the right child.
3. Binary Search Tree (BST): A special binary tree with ordering rules
4. AVL Tree: A self-balancing binary search tree
5. Heap: Used in priority queues
6. Trie: Used for dictionary and search suggestions
7. B-Tree: Used in databases and file systems