graph-traversal-challenge.js

// given a graph represented as a map of nodes and their children {node_1: [node_2, node_3]}, and two nodes a and b, write a function that returns a boolean indicating if node a is a descendant of node b

// isDescendant(graph, a, b) => returns true if a is a descendant of b

// Example
// g = {1: [2, 3], 2:[], 3:[4], 4:[5]}
// isDescendant(g, 5, 1) => true
// isDescendant(g, 2, 4) => false

    //   1
    //  / \
    // 2   3
    //     |
    //     4
    //     |
    //     5
    
function isDescendant (g, child, ancestor) {
    const keys = Object.keys(g)
    
    for (let leaf of g[ancestor]) {
        if (leaf === child) {
            return true
        } else {
            if (keys.includes(String(leaf)) && isDescendant(g, child, leaf)) {
                return true
            }
        }
    }
    
    return false
}

var g = {1: [2, 3], 2:[], 3:[4], 4:[5]}
console.log(isDescendant(g, 5, 1))
console.log(isDescendant(g, 2, 4))

/*

Alternative format, possibly overly-clever:

function isDescendant (g, child, ancestor) {
    const keys = Object.keys(g)
    
    for (let leaf of g[ancestor]) {
        if (leaf === child || (keys.includes(String(leaf)) && isDescendant(g, child, leaf))) {
            return true
        }
    }
    
    return false
}

*/