> For the complete documentation index, see [llms.txt](https://dsa-cpp.gitbook.io/nafees/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://dsa-cpp.gitbook.io/nafees/binary-tree/whats-binary-tree-and-implementation/traversal.md).

# 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.


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://dsa-cpp.gitbook.io/nafees/binary-tree/whats-binary-tree-and-implementation/traversal.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.