# BST In Order Traversal

BST Construction is covered here.

Sample tree:

```
5
/ \
2 9
/ \ \
1 3 10
```

## In Order traversal

The root element will be between the left and the right elements respectively.

`[1, 2, 3, 5, 9, 10]`

Note: In order traversal of a BST results in a sorted list.

## Recursive solution:

```
var traversal = []
function preorder(root) {
if (root == null) return
preorder(root.left)
traversal.push(root.val)
preorder(root.right)
}
```

## Iterative solution:

Depth first search, using a stack.

```
var traversal = []
var stack = []
while (stack.length != 0 || root != null) {
while (root != null) {
stack.push(root)
root = root.left
}
var node = stack.pop()
traversal.push(node.val)
root = node.right
}
```