# Traversals

There are a number of functions that can be written for a tree that involves iterating through all nodes of the tree exactly once. As it goes through each node exactly 1 time, the runtime should not exceed O(n)

These include functions such as print, copy, even the code for destroying the structure is a type of traversal.

Traversals can be done either depth first (follow a branch as far as it will go before backtracking to take another) or breadfirst, go through all nodes at one level before going to the next.

## Depth First Traversals

There are generally three ordering methods for depth first traversals. They are:

* preorder
* inorder
* postorder

In each of the following section, we will use this tree to describe the order that the nodes are "visited". A visit to the node, processes that node in some way. It could be as simple as printing the value of the node:

![](/files/-M66bFq8olhPRk_UCLnY)

### Preorder traversals

* visit a node
* visit its left subtree
* visit its right subtree

4, 2, 1, 3, 8, 6, 5, 7, 12, 11, 9, 10

### Inorder traversals:

* visit its left subtree
* visit a node
* visit its right subtree

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12

Notice that this type of traversal results in values being listed in its sorted order

### Postorder traversals:

* visit its left subtree
* visit its right subtree
* visit a node

1, 3, 2, 5, 7, 6, 10, 9, 11, 12, 8, 4

This is the type of traversal you would use to destroy a tree.

## Breadth-First Traversal

A breadfirst traversal involves going through all nodes starting at the root, then all its children then all of its children's children, etc. In otherwords we go level by level.

Given the following tree:

![](/files/-M66bFq8olhPRk_UCLnY)

A breadthfirst traversal would result in:

4, 2, 8, 1, 3, 6, 12, 5, 7, 11, 9, 10


---

# Agent Instructions: 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:

```
GET https://cathyatseneca.gitbook.io/data-structures-and-algorithms/introduction_to_trees-_binary_search_trees/binary_search_trees/traversals.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
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.