Trees

A graph is a collection of nodes and edges. A tree is a connected, acyclic, undirected graph. This means there is a path between every pair of distinct nodes, there are no cycles and you can go either way along an edge. A binary tree is one in which every node has at most 2 children.

Traversals

Any tree can be traversed in 2 ways - pre-order and post-order. A binary tree can also be traversed in-order.

Pre-order

In a pre-order traversal, the nodes are visited from top to bottom, left to right.

algorithm preOrder(v)
    print(v)
    for each child w of v
        preOrder(w)

Post-order

In a post-order traversal, the nodes are visited from bottom to top, left to right.

algorithm postOrder(v)
    for each child w of v
        postOrder(w)
    print(v)

In-order

In a pre-order traversal, the nodes are visited from top to bottom, left to right.

algorithm inOrder(v)
    if v.left exists
        inOrder(v.left)
    print(v)
    if v.right exists
        inOrder(v.right)

Decision trees

A decision tree is a binary tree in which each internal node is a question and each external node is an outcome. Decision trees can be used to find the lower bound for a sorting algorithm. If each external node in the tree is a possible ordering of the elements there must be $n!$ (from the definition of permutations) of them, giving a tree with height $\log(n!)$. This means any comparison based sorting algorithm takes at least $\log(n!)$ time. It can be shown that this means any comparison-based sorting algorithm must run in time $\Omega(n\log n)$, so $O(n \log n)$ is the most efficient comparison-based sorting algorithm time complexity.