### How to Recall Tree Traversal Orders

Let L denote the left child.

Let R denote the right child.

Let P denote the parent and position.

To easily remember tree traversal orders, pay attention to the position of P in the following strings.

When P is in the center, it is In Order. When it is first, it is Pre Order. And when it is last, it is Post Order.

L – P – R | In Order

P – L – R | Pre Order

L – R – P | Post Order

Note that L and R are always in the same order. The only element changing order is the parent.

### In Order

``leftChild -> parent -> rightChild``

Integer values come out in order when traversing a Binary Search Tree.

### Pre Order

``parent -> leftChild -> rightChild``

Traverse parent first (pre).

### Post Order

``leftChild -> rightChild -> parent``

Traverse parent last (post).

### Code

``````class BST {
var value: Int?
var left: BST?
var right: BST?

init(value: Int) {
self.value = value
left = nil
right = nil
}
}

// O(n) time | O(n) space, because we're storing all values in array
// Note: If were were just printing values, space will be O(h), where
// h is the height of the tree.

func inOrderTraversal(tree: BST?, array: inout [Int]) -> [Int] {
guard let node = tree, let value = node.value else { return array }

inOrderTraversal(tree: node.left, array: &array)
array.append(value)
inOrderTraversal(tree: node.right, array: &array)

return array
}

func preOrderTraversal(tree: BST?, array: inout [Int]) -> [Int] {
guard let node = tree, let value = node.value else { return array }

array.append(value)
preOrderTraversal(tree: node.left, array: &array)
preOrderTraversal(tree: node.right, array: &array)

return array
}

func postOrderTraversal(tree: BST?, array: inout [Int]) -> [Int] {
guard let node = tree, let value = node.value else { return array }

postOrderTraversal(tree: node.left, array: &array)
postOrderTraversal(tree: node.right, array: &array)
array.append(value)

return array
}`````` ### David Inga

Designed by David Inga in California.