2.3 - Tree & Graph Traversal Algorithms.md

Tree/Graph Traversal Algorithms

Breadth-First Traversal

• An algorithm that traverses through a tree (or graph) level-by-level, starting at the root.
• Breadth-First Traversal is iterative and uses a queue to keep track of unvisited nodes.
• In a tree, the bottom-right node is evaluated last (i.e. the node that is deepest and is farthest right).

Binary Tree BFT

// Breadth-First Traversal of a Binary Tree
void BFTraversal(BTNode root) {
    Queue<BTNode> queue = new LinkedList<BTNode>();
    queue.add(root);

    while (!queue.isEmpty()) {
        BTNode node = queue.poll();  // poll() removes the present head
        System.out.println(node.data);

        // Enqueue left child
        if (node.left != null) queue.add(node.left);

        // Enqueue right child
        if (node.right != null) queue.add(node.right);
    }
}

Graph BFS

// Breadth-First Search of a Graph
void BFS(Node root) {
    Queue<Node> queue = new LinkedList<Node>();
    root.visited = true;
    queue.add(root);

    while(!queue.isEmpty()) {
        Node r = queue.poll();
        visit(r);

        for (int i = 0; i < root.adjacent.length; i++) {
            if (root.adjacent[i].visited == false) {
                root.adjacent[i].visited = true;
                queue.add(root.adjacent[i]);
            }
        }
    }
}

Time Complexity

O(|V| + |E|)

Depth-First Traversal

• An algorithm that traverses through a tree (or graph) by traversing the depth of the tree first, starting at the root.
• Depth-First Traversal is usually recursive and uses a stack to keep track of unvisited nodes.
• In pre-order & in-order traversal, the right-most node is evaluated last (the node that is right of all its ancestors).
• In post-order traversal, the root node is evaluated last.

Pre-Order Traversal

1. Process the current node.
2. Visit the left child subtree.
3. Visit the right child subtree.

In-Order Traversal

1. Visit the left child subtree.
2. Process the current node.
3. Visit the right child subtree.

Post-Order Traversal

1. Visit the left child subtree.
2. Visit the right child subtree.
3. Process the current node.

Binary Tree DFT (Recursive)

// Pre-Order Depth-First Traversal of a Binary Tree
void DFTraversal(BTNode node) {
    if (node == null) return;

    System.out.println(node.data);  // visit node
    DFTraversal(node.left);         // left subtree
    DFTraversal(node.right);        // right subtree
}

Binary Tree DFT (Iterative)

// Iterative Pre-Order DFT of a Binary Tree
void IterativePreOrderDFT(BTNode node) {
    if (node == null) return;

    // The stack will keep track of the order to visit the nodes, from top to bottom.
    Stack<BTNode> stack = new Stack<>();
    stack.push(root);

    // Traverse the tree.
    while (!stack.isEmpty()) {
        BTNode node = stack.pop();
        System.out.print(node.data + " ");

        // Push right then left child to stack so left child is visited first.
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
}

// Iterative In-Order DFT of a Binary Tree
void IterativeInOrderDFT(BTNode node) {
    if (root == null) return;

    // The stack will keep track of the order to visit the nodes, from top to bottom.
    Stack<BTNode> stack = new Stack<>();
    BTNode node = root;

    // Set the top of the stack to the leftmost node.
    while (node != null) {
        stack.push(node);
        node = node.left;
    }

    // Traverse the tree.
    while (!stack.isEmpty()) {
        node = stack.pop();
        System.out.print(node.data + " ");

        if (node.right != null) {
            node = node.right;
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
        }
    }
}

// Iterative Post-Order DFT of a Binary Tree
void IterativePostOrderDFT(BTNode node) {
    if (root == null) return;

    // The stack will keep track of the order to visit the nodes, from top to bottom.
    Stack<BTNode> stack = new Stack<>();
    stack.push(root);

    BTNode prev = null;
    while (!stack.isEmpty()) {
        BTNode curr = stack.peek();

        // Go down the tree. If current node is leaf, process it and pop stack,
        // otherwise, keep going down.
        if (prev == null || prev.left == curr || prev.right == curr) {
            if (curr.left != null) {
                stack.push(curr.left);
            } else if (curr.right != null) {
                stack.push(curr.right);
            } else {
                System.out.println(curr.data);
                stack.pop();
            }

        // Go up the tree from the left node. If there is a right child, push it
        // onto stack. Else, process parent node and pop stack.
        } else if (curr.left == prev) {
            if (curr.right != null) {
                stack.push(curr.right);
            } else {
                System.out.println(curr.data);
                stack.pop();
            }

        // Go up the tree from the right node. Process parent node and pop stack.
        } else if (curr.right == prev) {
            System.out.println(curr.data);
            stack.pop();
        }

        prev = curr;
    }
}

Graph DFS

// Depth-First Search of a Graph
void DFS(Node root) {
    if (root == null) return;

    visit(root);
    root.visited = true;

    for (int i = 0; i < root.adjacent.length; i++) {
        if (root.adjacent[i].visited == false) DFS(root.adjacent[i]);
    }
}

Time Complexity

O(|V| + |E|)

BFS vs. DFS & Other Search Algorithms

• Breadth-first search is guaranteed to find a shortest possible path between two vertices in a graph. Depth-first search is not (and usually does not).
• Iterative deepening depth-first search is a graph search strategy in which a depth-limited version of depth-first search is run repeatedly with increasing depth limits until the goal is found. This is equivalent to breadth-first search but uses much less memory since on each iteration, it visits the nodes in the search tree in the same order as depth-first search but the cumulative order in which nodes are visited is effectively breadth-first.
• Bidirectional search is used to find the shortest path between a source and a destination node. It operates by essentially running two simultaneous breadth-first searches, one from each node. When the searches collide, the path is found.