_es6-BFS-DFS.js - Using ES6 for breadth-frist-search and depth-first-search.

_es6-BFS-DFS.js

// getChildren(win) - returns array of windows that are child to `win`
// isTrue(win) - just a random callback

function recurseDFS(win) {
	// depth first
	let coll = [];
	coll.push(isTrue(win));
	let children = getChildren(win);
	for (let child of children) {
		coll.push(...recurseDFS(child));
	}
	return coll;
}

function recurseBFS(win) {
	// breadth first
	let coll = [];
	let todo = [win];

	while (todo.length) {
		let cur = todo.shift();
		coll.push(isTrue(cur));
		todo.push(...getChildren(cur));
	}
	
	return coll;
}

/////// actually usable stuff, will stop recursion, and get actual data from the callback
// doCallback - function. arguments: win, depth. return: object;{data:any, done:bool} - set `done` to true if you want to stop recursion, if `data` is not set, then nothing is pushed to `coll` for that recurse. so if you want to not stop recursion and not collect for the current recurse, it is fine ok to not return anything from the callback.

function recurseDFS(win, doCallback, progstopref, progdepth=0) {
	// progstopref - used programatically, devuser should never pass it
	// progdepth - use programatically, devuser should never pass it
	
	let stop = progstopref || {yes:false};
	let depth = progdepth;
	
	let coll = [];
	if (stop.yes) return coll;

	let rez = doCallback(win, depth);
	if (rez && rez.data) coll.push(rez.data);
	if (rez && rez.done) {
		stop.yes = true;
	} else {
		let children = getChildren(win);
		for (let child of children) {
			coll.push(...recurseDFS(child, stop, depth+1));
		}
	}
	
	return coll;
}

function recurseBFS(win, doCallback) {
	let coll = [];
	let todo = [];
	let depth = -1;
	let next_depth = [win]; // holds the current `win`'s at current `depth`

	breakpoint: {
		while (next_depth.length) {
			depth++;
			todo.push(...next_depth);
			next_depth.length = 0; // next_depth.splice(0, next_depth.length); // empty `next_depth`
			while (todo.length) {
				let cur = todo.shift();
				let rez = doCallback(win, depth);
				if (rez && rez.data) coll.push(rez.data);
				if (rez && rez.done) break breakpoint;
				next_depth.push(...getChildren(cur));
			}
		}
	}
	
	return coll;
}

README

Rev3

• Finished recurseBFS
• Fixed typo in recurseDFS

Rev4

• Untested, but added bottom half section, which is hooked up so can actually pass a callback, and collect real data, and stop recursion
• getChildren is still an imaginary function

Rev5

• Touched up in bottom half
• Noted that its possible to not return anything from callback, made recurseDFS handle getting undefined from a callback as a return value
• Style touch up in recurseBFS

function Node(data, left=null, right=null) {
    this.data = data;
    this.left = left;
    this.right = right;
}

var tree =
// new Node(5,
//     new Node(4,
//         new Node(3,
//             new Node(2,
//                 new Node(1,
//                     new Node(0,
//                         null,
//                         null
//                     ),
//                     new Node(2,
//                         null,
//                         null
//                     )
//                 ),
//                 new Node(3,
//                     null,
//                     null
//                 )
//             ),
//             new Node(4,
//                 null,
//                 null
//             )
//         ),
//         new Node(5,
//             new Node(4,
//                 null,
//                 null
//             ),
//             new Node(6,
//                 null,
//                 null
//             )
//         )
//     ),
//     new Node(
//         6,
//         new Node(5,
//             null,
//             null
//         ),
//         new Node(7,
//             new Node(6,
//                 new Node(5,
//                     null,
//                     null
//                 ),
//                 new Node(7,
//                     null,
//                     null
//                 )
//             ),
//             new Node(8,
//                 new Node(7,
//                     null,
//                     null
//                 ),
//                 new Node(9,
//                     new Node(8,
//                         null,
//                         null
//                     ),
//                     new Node(10,
//                         null,
//                         null
//                     )
//                 )
//             )
//         )
//     )
// )
// new Node(4,
//     new Node(
//         2,
//             new Node(
//                 1,
//                 null,
//                 null
//             ),
//             new Node(
//                 3,
//                 null,
//                 null
//             )
//     ),
//     new Node(
//         6,
//             new Node(
//                 5,
//                 null,
//                 null
//             ),
//             new Node(
//                 7,
//                 null,
//                 null
//             )
//     )
// )
new Node(7,
    new Node(
        4,
            new Node(
                2,
                    new Node(
                        1,
                        null,
                        null
                    ),
                    new Node(
                        3,
                        null,
                        null
                    )
            ),
            new Node(
                6,
                    new Node(
                        5,
                        null,
                        null
                    ),
                    new Node(
                        7,
                        null,
                        null
                    )
            )
    ),
    new Node(
        10,
            new Node(
                8,
                    new Node(
                        7,
                        null,
                        null
                    ),
                    new Node(
                        9,
                        null,
                        null
                    )
            ),
            new Node(
                12,
                    new Node(
                        11,
                        null,
                        null
                    ),
                    new Node(
                        13,
                        null,
                        null
                    )
            )
    )
)

console.log('tree:', tree);

function printBFS(root) {
    const datas = [];

    var nodes = [root];
    while (nodes.length) {
        var node = nodes.shift();
        datas.push(node.data);
        if (node.left) {
            nodes.push(node.left);
        }
        if (node.right) {
            nodes.push(node.right);
        }
    }

    console.log('datas:', datas);
}

function printDFS(root) {
    const datas = [];

    var nodes = [root];
    while (nodes.length) {
        var node = nodes.pop();
        datas.push(node.data);
        if (node.right) {
            nodes.push(node.right);
        }
        if (node.left) {
            nodes.push(node.left);
        }
    }

    console.log('datas:', datas);
}

printNodesPerLevel a BFS application:

function Node(data, left=null, right=null) {
    this.data = data;
    this.left = left;
    this.right = right;
}

var tree =
new Node(
    7,
        new Node(
            4,
                new Node(
                    2
                )
        ),
        new Node(
            10
        )
)

console.log('tree:', tree);

function printNodesPerLevel(root) {
    const nodesPerLevel = [];

    var nodes = [root];
    var nextNodes = [];
    var nodesThisLevel = 0;
    while (nodes.length) {
        nodesThisLevel++;
        var node = nodes.shift();
        if (node.left) {
            nextNodes.push(node.left);
        }
        if (node.right) {
            nextNodes.push(node.right);
        }
        if (!nodes.length) { // level complete
            nodesPerLevel.push(nodesThisLevel);
            nodes.push(...nextNodes);
            nextNodes.length = 0;
            nodesThisLevel = 0;
        }
    }

    console.log('nodesPerLevel:', nodesPerLevel);
}

function bfs(parentNode) {
    // sdl - stack DFS LIFO
    // qbf - queue BFS FIFO

    const queue = [parentNode];
    const nodesCollectedBreadthFirst = [];

    while (queue.length) {
        const node = queue.shift();
        nodesCollectedBreadthFirst.push(node);
        queue.push(...node.childNodes);
    }

    return nodesCollectedBreadthFirst;
}

function dfs(parentNode) {
    // sdl - stack DFS LIFO
    // qbf - queue BFS FIFO

    const stack = [parentNode];
    const nodesCollectedDepthFirst = [];

    while (stack.length) {
        const node = stack.pop();
        nodesCollectedDepthFirst.push(node);
        stack.push(...node.childNodes);
    }

    return nodesCollectedDepthFirst;
}

https://www.programmerinterview.com/index.php/data-structures/dfs-vs-bfs/