# Traversal

In a Binary Search Tree (BST), there are several ways to traverse the nodes in a specific order. The most common traversal methods are Inorder, Preorder, Postorder, and Level Order traversals. Here's a detailed explanation of each:

## <mark style="color:blue;">Inorder Traversal</mark>

In an inorder traversal, the nodes are visited in the following order: **Left subtree -> Root -> Right subtree**. This traversal method results in the nodes being visited in ascending order if it's a BST.

**Algorithm:**

1. Traverse the left subtree recursively.
2. Visit the root node.
3. Traverse the right subtree recursively.

**Example:** For the following BST:

```
    4
   / \
  2   6
 / \ / \
1  3 5  7
```

The inorder traversal would be: 1, 2, 3, 4, 5, 6, 7

## <mark style="color:blue;">Preorder Traversal</mark>

In a preorder traversal, the nodes are visited in the following order: **Root -> Left subtree -> Right subtree**. This traversal method is often used to create a copy of the tree.

**Algorithm:**

1. Visit the root node.
2. Traverse the left subtree recursively.
3. Traverse the right subtree recursively.

**Example:** For the same BST:

```
    4
   / \
  2   6
 / \ / \
1  3 5  7
```

The preorder traversal would be: 4, 2, 1, 3, 6, 5, 7

## <mark style="color:blue;">Postorder Traversal</mark>

In a postorder traversal, the nodes are visited in the following order: **Left subtree -> Right subtree -> Root**. This traversal method is useful for deleting nodes in a tree.

**Algorithm:**

1. Traverse the left subtree recursively.
2. Traverse the right subtree recursively.
3. Visit the root node.

**Example:** For the same BST:

```
    4
   / \
  2   6
 / \ / \
1  3 5  7
```

The postorder traversal would be: 1, 3, 2, 5, 7, 6, 4

## <mark style="color:blue;">Level Order Traversal</mark>

In a level order traversal, the nodes are visited level by level from left to right. This traversal method is also known as <mark style="color:red;">Breadth-First Search (BFS).</mark>

**Algorithm:**

1. Start from the root node.
2. Use a queue to keep track of nodes at each level.
3. Dequeue a node, visit it, and enqueue its left and right children.
4. Repeat the process until the queue is empty.

**Example:** For the same BST:

```
    4
   / \
  2   6
 / \ / \
1  3 5  7
```

The level order traversal would be: 4, 2, 6, 1, 3, 5, 7

These traversal methods allow different ways of accessing and processing all the nodes in a BST, each with its own unique order and use cases.