In-Order-Traversal

• left, node, right

void inOrderTraversal(TreeNode node) {
    if(node!=null) {
        inOrderTraversal(node.left);
        visit(node);
        inOrderTraversal(node.right);
    }

}

When performed on a binary search tree, it visits the nodes in ascending order(hence the name in-order).

Pre-order Traversal

• node, left, right

void preOrderTraversal(TreeNode node) {
    if (node!=null) {
        visit(node);
        preOrderTraversal(node.left);
        preOrderTraversal(node.right);
    }
}

In a pre-order traversal, the root is always the first node visited.

Post-order Traversal

• left, right, node

void postOrderTraversal(TreeNode node) {
    if(node!=null){
        postOrderTraversal(node.left);
        postOrderTraversal(node.right);
        visit(node);
    }
}

In post-order traversal, the root is always the last node visited

Depth-First Search (DFS) --- using recursion

In DFS, we visit a node a and then iterate through each of a's neighbors. When visiting a node b that is a neighbor of a, we visit all b's neighbors before going on to a's other neighbor.

Note that in-order, pre-order and post-order are a form of DFS. The key difference is that when implementing this algorithm for a graph, we must check if the node has been visited. If we don't, we risk getting stuck in an infinite loop.

pseudocode:

void dfsSearch(Node root) {
    if (root == null) return;
    visit(root);
    root.visited = true;
    for each (Node n in root.adjacent) {
        if (n.visited == false) {
            search(n);
        }
    }
}

Breath-First Seach(BFS) --- using iteration

Uses a queue to implement.

In BFS, node A visits each of a's neighbors before visiting any of their neighbors. You can think of this as searching level by level out from A.

pseudocode:

void bfsSearch(Node root) {
    Queue queue - new Queue();
    root.marked = true;
    queue.enqueue(root); //add to the end of queue

    while (!queue.isEmpty()) {
        Node r = queue.dequeue(); //remove from the front of the queue
        visit(r);
        for each (Node n in r.adjacent) {
            if(n.marked == false) {
                n.marked = true;
                queue.enqueue(n);
            }
        }
    }
}