Cracking the Coding Interview - 4 Trees and Graphs

In [9]:

    

var Node = val => {
    let value = val
    let left = null
    let right = null
    const getValue = () => value
    const setValue = newVal => {value = newVal}
    const getLeft = () => left
    const getRight = () => right
    const setLeft = Node => {left = Node}
    const setRight = Node => {right = Node}
    return{getValue, setValue, getLeft, getRight, setLeft, setRight}
}


    

In [10]:

    

var InOT = node => {
    if (node) {
        InOT(node.getLeft())
        console.log(node.getValue())
        InOT(node.getRight())
    }
}


    

In [11]:

    

var PreOT = node => {
    if (node) {
        console.log(node.getValue())
        PreOT(node.getLeft())
        PreOT(node.getRight())
    }
}


    

In [12]:

    

var PostOT = node => {
    if (node) {
        PostOT(node.getLeft())
        PostOT(node.getRight())
        console.log(node.getValue())
    }
}


    

In [13]:

    

var myNode = Node(10)
myNode.setLeft(Node(5))
myNode.getLeft().setLeft(Node(3))
myNode.getLeft().setRight(Node(7))
myNode.setRight(Node(20))


    

In [14]:

    

InOT(myNode)


    

    




3
5
7
10
20

In [ ]:

    

var Node = val => {
    let value = val
    let children = []
    const getValue = () => value
    const getChildren = () => children
    const setValue = newVal => {value = newVal}
    const addChild = childNode => {children.push(childNode)}
    return {getValue, getChildren, setValue, addChild}
}

var Graph = () => {
    let nodes = []
    const getNodes = () => nodes
    const addNode = node => {nodes.push(node)}
    return {getNodes, addNode}
}


    

In [123]:

    

var AMatrix = () => {
    let matrix = new Map()
    const set = (fromNode, toNode) => {
        if (!matrix.get(fromNode)){
            matrix.set(fromNode, new Map())
        }
        matrix.get(fromNode).set(toNode, true)
    }
    const get = (fromNode, toNode) => {
        if (matrix.get(fromNode)){
            if (matrix.get(fromNode).get(toNode)){
                return true
            }
        }
        return false
    }
    const keys = () => matrix.keys()
    const keysFor = fromNode => {
        if (matrix.has(fromNode)){
            return matrix.get(fromNode).keys()
        }
        return []
    }
    return {set, get, keys, keysFor}
}


    

In [124]:

    

var myAMatrix = AMatrix()


    

In [125]:

    

for ([k, v] of [[1, 3], [2, 3], [1, 6], [6, 2]]) {
    myAMatrix.set(k, v)
}


    

In [126]:

    

myAMatrix.get(1, 3)


    

    
Out[126]:





true

In [127]:

    

myAMatrix.get(2, 6)


    

    
Out[127]:





false

In [128]:

    

myAMatrix.keys()


    

    
Out[128]:





MapIterator { 1, 2, 6 }

In [129]:

    

myAMatrix.keysFor(1)


    

    
Out[129]:





MapIterator { 3, 6 }

In [130]:

    

for (key of myAMatrix.keysFor(1)) {
    console.log(key)
}


    

    




3
6

In [109]:

    

var hasRoute = (amatrix, a, b) => {
    const visited = new Map()
    visited.set(a, true)
    const q = []
    q.push(a)
    while (q.length){
        let current = q.shift()
        if (current === b) {
            return true
        }
        for (next of amatrix.keysFor(current)){
            if (!visited.get(next)){
                visited.set(next, true)
                q.push(next)
            }
            
        }
    }
    return false
}


    

In [120]:

    

var myAMatrix = AMatrix()
for (var nodePair of [
    [0, 1],
    [0, 5],
    [0, 4],
    [1, 3],
    [1, 4],
    [2, 1],
    [3, 2],
    [3, 4]
]){
    myAMatrix.set(nodePair[0], nodePair[1])
}


    

In [122]:

    

for (var [a, b] of [
    [2, 5],
    [0, 5],
    [5, 0],
    [4, 5],
    [0, 3],
    [3, 0]
]){
    console.log(a + ", " + b + " => " + hasRoute(myAMatrix, a, b))
}


    

    




2, 5 => false
0, 5 => true
5, 0 => false
4, 5 => false
0, 3 => true
3, 0 => false

In [ ]: