# Tree data structure

## What is tree?

A tree is a hierarchical data structure that consists of nodes connected by edges. It is NOT a linear data structure.

#### Node

Element in a tree

#### Root

The node at the top of the tree is called the root. There is only one root per tree and one path from the root node to any node.

#### Parent

Any node except the root node has one edge upward to a node called the parent.

#### Child

The node below a given node connected by its edge downward is called its child node.

#### Subtree

Subtree represents the descendants of a node.

#### Visiting

Visiting refers to checking the value of a node when control is on the node.

#### Traversing

Traversing means passing through nodes in a specific order.

#### Levels

The Level of a node represents the generation of a node. If the root node is at level 0, then its next child node is at level 1, its grandchild is at level 2, and so on.

#### Keys

The key represents a value of a node based on which a search operation is to be carried out for a node.

#### Leaf nodes:

Leaf nodes are nodes that are on the bottom of the tree and have no children.

#### Node Depth:

Node depth is the number of links from the root to the node.

#### Tree Height:

Tree height is the number of links from its root to the furthest leaf. The tree height is the same as the maximum node depth.

## Examples of Tree data structure

The tree data structure is widely used in many areas of computer science. The following are some examples of tree data structure:

## Tree Traversal classification

Tree Traversal algorithms can be classified broadly into two categories:

- Depth-First Search (DFS) Algorithms
- Breadth-First Search (BFS) Algorithms

### Depth-First Search (DFS) Algorithms

Depth-First Search (DFS) Algorithms have three variants:

**Preorder Traversal (current-left-right)**— Visit the current node before visiting any nodes inside the left or right subtrees.

**Inorder Traversal (left-current-right)**— Visit the current node after visiting all nodes inside the left subtree but before visiting any node within the right subtree.

**Postorder Traversal (left-right-current)**— Visit the current node after visiting all the nodes of the left and right subtrees.

### Breadth-First Search (BFS) Algorithms

Breadth-First Search (BFS) Algorithm has one variant:

**Level Order Traversal**— Visit nodes level-by-level and left-to-right fashion at the same level.