[Data Structures] Binary Tree Traversals with Implementations

In Order: visit the left branch, then the current node, and finally visit the right branch.

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

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

Pre Order: visits the current node before its child nodes (hence the name "pre-order")

• The root is always the first node visited.

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

Post Order: visit the current node after its child nodes

• The root is always the last node visited.

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

Depth First Search (DFS)

We visit a node a then iterate through each of a's neighbors. When vising a node b that is a neighbor of a, we visit all of b's neighbors before going on to a's other neighbors. That is, a exhaustively searches b's branch before any of its other neighbors. 

 

A node that pre-order and other forms of tree traversal 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. 

 

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

Breadth-First Search (BFS)

BFS is a bit less intuitive and many interviewees struggle with the implementation unless they are already familiar with it. The main tripping point is the (false) assumption that BFS is recursive. It's not. Instead, it uses a queue.

 

In BFS, node a visits each of a's neighbors before vising any of their neighbors. You can think of this as searching level by level out from a. An interactive solution involving a queue usually works best.

void BFS_Search(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);
        foreach (Node n in r.adjacent) {
            if (n.marked == false) {
                n.marked = true;
                queue.enqueue(n);
            }
        }
    }
}

The key to remember is the use of the queue.