### Tree Data Structure and its Applications

## What is Tree Data Structure?

A tree is a non-linear data structure as it stores data in a **hierarchical manner that consists of nodes connected through edges.**

It is the best alternative for the linear data structure like **arrays, stacks, queues, etc **as these linear data structures have high time and space complexity.

The data stored in nodes of the tree are easier to access thus reducing the time complexity.

### Terms related to tree data structure

#### 1. Node

#### 2. Edge

#### 3. Root

**1**is the Root node.

#### 4. Parent and Child Node

The node which contains sub-nodes is called the parent node. Here 1 is the parent node for **2** and **3** and **2** is the parent node for **4 **and **5.**

The node which is a descendant of any node is called a child node. Here **2** and **3 **are child nodes and 1 and **4** and **5** are child nodes of **2**.

#### 5. Internal node

**1**is an internal node whereas

**3**is not an internal node.

#### 6. Leaf node (external node)

#### 7. Height of a node

**node 1**and

**node 2.**The height of node

**2 is 1.**

#### 8. Depth of a node

**node 2**is

**1**. The depth of

**node 5**is

**2.**

#### 9. Height of a tree

**2.**

#### 10. Degree of node

**node 1**has

**2 degrees**. Node 3 has

**0**degrees as no branches are there.

### Application of a Tree

1. Trees are used to quickly check whether a data element is present in the set or not.

2. Heap tree is used to perform heap sort of elements.

3. A modified version of a tree, called tries, is utilized in modern routers for storing routing information.

4. Compilers use a syntax tree to validate the syntax of every program.