A tree is a Data Structure composed of nodes, where each node is a data structure consisting of value, together with a list of references to the children

Properties of the tree data structure:

- Each tree has a root node.
- If a tree has n nodes, then it will have (n-1) edges only.
- A node with degree 0(or no children) is called a leaf node.
- A m-ary tree can have at most m children ( maximum degree m). Ex: 2-ary or Binary Tree can have at most 2 children only.
- A path is the length of edges between source node to other destination nodes.
- The height of a tree represents the number of edges on the longest path between the root node and a leaf. The height of leaf nodes is always 0.
- The level of a tree is always height + 1.
- Max no. of leaf nodes
**L= n(m-1) + 1**. Here**m**represents m-ary tree(m=2 for a binary tree, m=3 for ternary tree and so on), and**n**is the number of internal nodes with degree m.

**Example**

Following is a Ternary (3-ary) Tree

The maximum degree of a node is 3.(Node 7 has max degree 3).

The height of the tree is 3.(Following are the path with maximum path length so will count them towards height *2->7->6->5 *or *2->7->6->11* or *2->5->9->1*).

*2(marked red)* is the root node with height 3. 2, *10, 5, 11, 4* are the leaf nodes with height 0.

**Important terminologies related to Tree Data Structure**

**Node: **A node is a structure that may contain a value.

**Root:** The top node in a tree.

**Child: **A node directly connected to another node when moving away from the root, an immediate descendant.

**Parent: **The converse notion of a child, an immediate ancestor.

**Siblings: **A group of nodes with the same parent.

**Ancestor: **A node reachable by repeated proceeding from child to parent.

**Leaf node: **A node with no children.

**Internal node: **A node with at least one child.

**Degree: **For a given node, its number of children. A leaf is necessarily degree zero. The degree of a tree is the degree of its root.

**Edge: **The connection between one node and another

**Sub Tree: **A tree *T* is a tree consisting of a node in *T* and all of its descendants in *T*.

**Application of Tree Data Structure**

- Store hierarchical data, like folder structure, organization structure, XML/HTML data
- Heap is a tree data structure that is implemented using arrays and used to implement priority queues.
- Trie Used to implement dictionaries with prefix lookup.
- Spanning Trees and shortest-path trees are used in routers and bridges respectively in computer networks
- B-Tree and B+ Tree They are used to implement indexing in databases.
- Binary Search Tree is a tree that allows fast search, insert, delete on sorted data. It also allows finding the closest item
- Representing sorted lists of data.
- Creating Binay & Binary Search Tree.