FindNodeBFS.ts

/**
 * Finds a node from a tree-like datastructure
 * 
 * Could be easily implemented as DFS by switching `stack.shift()` to `stack.pop()`
 * 
 * @param rootNode Root node of the tree-like datastructure
 * @param obtainChildren Return children of a given node
 * @param test Return true if the given node is the searched for one
 * @returns {?T} the given node if found or null
 */
function FindNodeBFS<T>(
        rootNode: T,
        obtainChildren: (node: T) => Array<T>,
        test: (node: T) => Boolean): T {

    const stack: Array<T> = []

    stack.push(rootNode)
    while(stack.length > 0) {
        const node = stack.shift() // Using shift (queue-like) for BFS, alternatively use pop for DFS

        if (test(node)) {
            return node
        }

        obtainChildren(node).forEach(child => stack.push(child))
    }

    return null
}