Binary Tree Traversal

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
}