Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
_es6-BFS-DFS.js - Using ES6 for breadth-frist-search and depth-first-search.
// 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;
}
Owner

Noitidart commented Dec 6, 2016

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
Owner

Noitidart commented Jul 21, 2017

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);
}
Owner

Noitidart commented Nov 5, 2017

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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment