The tree is one of the most used Data Structures and there are many real-world solutions based on this data structure. Though we have Data structures like an array and linked list to store data, the time complexity of searching an element from an array and list have linear time complexity. Suppose there is a list or array with n number of elements or sets, then the number of comparisons needed to find (or not find) an element may be n. So, imagine searching for an element in a linked list (or array) with n = 10 6 nodes. Even on a machine that can do a million comparisons per second, searching for m items will take roughly m seconds. Therefore, we require a better data structure to store and search data. Here in this article, we have provided a brief explanation of what is a Tree Data Structure and why we use it.
What is Tree Data Structure?
A Tree is a Non-Linear, data structure and it is a collection of nodes and edges, the edges could be directed or undirected. The tree follows a hierarchical structure and does not form any closed loop. In the tree, there is only one root node which is also known as the first or head node of the tree data structure and each node is the child node of it. A Tree can also be defined as the recursive collection of nodes where each node has a parent node except the root node.
Tree Properties
- If a tree has one node it would be the root node.
- A tree does not form a closed-loop structure.
- Every node is connected by one node.
- Each node of a tree can have an arbitrary number of child nodes.
- A tree with its disjoint subtree is known as a forest.
Basic Tree Terminology
| Node | A node is a separate data structure that contains data or value for a tree. |
| Root | The top node in a tree. |
| Child | A node connected to the previous node is known as the child node, each node in the tree is the child node of the root node |
| Parent | It is opposite of the Child node; a parent node is the main node which is connected to the further child node. |
| Siblings | Two or more than two nodes with the same parent node are the sibling’s node |
| Leaf / External node (not common) | The node in the tree data structure which has no further child node |
| Branch node / Internal node | A node with at least one child. |
| Edge | The connection between one node and another. |
| Path | A sequence of nodes and edges connecting a node with a descendant. |
| Distance | The number of edges along the shortest path between two nodes. |
| Depth | The distance between a node and the root. |
| Height | The number of edges on the longest path between a node and a descendant leaf. |
| Height of tree | The height of the root node or the maximum level of any node in the tree |
| Sub Tree | A tree T is a tree consisting of a node in T and all of its descendants in T . |
| Size of a tree | The total number of nodes present in the tree. |
Types of Tree
Here are some basic types of Tree data structure:
- General Tree
- Binary Tree
- Binary Search Tree
General Tree
In General Tree, each node could have zero or more than zero child node.
Binary Tree
In the binary tree, each node could not have more than two nodes.
Binary Search Tree
A binary search tree is an ordered binary tree in which each node on the left side of the root node is less than root node and the nodes on the right side of the root node are greater than root node.
Advantages of Tree
- In the tree, the same node shows multiple relations
- Provides a hierarchical structure
- Provides efficient insertion and deletion operations
People are also reading: