In this tutorial, you will learn about **tree data structure**. Additionally, you will learn about various types of trees and the terminologies used in trees.

Contents

## What are trees?

The tree represents the nodes associated with edges. We will talk about the binary tree or binary search tree especially.

A binary Tree is a special data structure used for data storage purposes. A binary tree has a special condition that every node can have a maximum of two kids. A binary tree has the advantages of both an arranged array and a linked list as search is pretty much as brisk as in an arranged array and insertion or erasure activity are just about as quick as in the linked list.

A tree is a nonlinear hierarchical data structure that comprises nodes associated with edges.

## Why Tree Data Structure?

Other data structures, for example, arrays, linked list, stack, and queue are linear data structures that store data sequentially. To play out any activity in a linear data structure, the time intricacy increments with the increment in the data size. Be that as it may, it isn’t worthy in the present computational world.

Different tree data structures allow quicker and simpler access to the data as it is a non-linear data structure.

## Tree Terminologies

### Node

A node is an entity that contains a key or value and pointers to its child nodes.

The last nodes of each path are called** leaf nodes or external nodes** that don’t contain a link/pointer to kid nodes.

The node having in any event a child node is called an **internal node**.

### Edge

It is the link between any two nodes.

### Root

It is the highest node of a tree.

### Height of a Node

The height of a node is the quantity of edges from the node to the most profound leaf (ie. the longest way from the node to a leaf node).

### Depth of a Node

The depth of a node is the number of edges from the root to the node.

## Height of a Tree

The height of a Tree is the height of the root node or the profundity of the most profound node.

### Degree of a Node

The degree of a node is the total number of branches of that node.

### Forest

A collection of disjoint trees is called a forest.

You can create a forest by cutting the root of a tree.

## Tree Traversal

To play out any procedure on a tree, you need to reach to the particular node. The tree traversal algorithm helps in visiting a necessary node in the tree.

## Tree Applications

- Binary Search Trees(BSTs) are used to rapidly check if an element is available in a set.
- Heap is a sort of tree that is used for heap sort.
- A changed rendition of a tree called Tries is used in present-day routers to store routing data.
- Most famous databases use B-Trees and T-Trees, which are variations of the tree structure we learned above to store their information
- Compilers use a syntax tree to approve the syntax of each program you write.

Thanks for reading! We hope you found this tutorial helpful and we would love to hear your feedback in the Comments section below. And show us what you’ve learned by sharing your photos and creative projects with us.