You've successfully subscribed to Nicholas Workshop
Great! Next, complete checkout for full access to Nicholas Workshop
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

Breathe First Traversal

Nicholas Wong
Nicholas Wong

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

Algorithm

Nicholas Wong

Fullstack software engineer with strong background in computer science and extensive experience in software engineering and architecture. Studied in NYU, worked in Yahoo, Rakuten and Manulife.