Breathe first traversal

In the iterative way

You can only do breathe first traversal in iterative way. Though you can still make it recursive by calling itself in each loop, but you will not benefit from it. It is similar to doing depth first traversal, instead you use a FIFO queue to store the nodes.

Breathe first iterative traversal

This example travel all nodes in the given tree, and return a list of values in the traveling order.

class Node {
    value: number;
    left: Node;
    right: Node;
}

function travel(root: BinaryTreeNode): number[] {
    let queue = [root];
    let result = [];
    while (queue.length > 0) {
        let node = queue.shift();
        if (node != null) {
            visit(node, result);
            queue.push(node.left, node.right)
        }
    }
    return result;
}

function visit(node: BinaryTreeNode, result: number[]) {
    result.push(node.value);
}

Full example

https://github.com/nickwph/algorithm-ts/blob/master/src/binary-tree/bfs-iterative.binary-tree.ts

Show Comments