tree traversal implementations

readme.md

Обход в глубину с рекурсией

function dfsWalkRecursive(node) {
  console.log(node.value)
  if(node.children) node.children.forEach(childNode => dfsWalkRecursive(childNode))
}


const tree = {
    value: 1,
    children: [
        {
            value: 2,
            children: [
                {
                    value: 3,
                    children: [{ value: 4 }, { value: 5 }, { value: 6 }]
                },
                {
                    value: 7
                }
            ]
        }
    ]
}

dfsWalkRecursive(tree)

Обход в глубину без рекурсии

function dfsWalk(tree) {
    const queue = [tree]

    while (queue.length) {
        const node = queue.pop()
        console.log(node.value)
        if (node.children) queue.push(...node.children.reverse())
    }
}

const tree = {
    value: 1,
    children: [
        {
            value: 2,
            children: [
                {
                    value: 3,
                    children: [{ value: 4 }, { value: 5 }, { value: 6 }]
                },
                {
                    value: 7
                }
            ]
        }
    ]
}

dfsWalk(tree)

Обход в ширину без рекурсии

function bfsWalk(tree) {
    const queue = [tree]

    while (queue.length) {
        const node = queue.shift()
        console.log(node.value)
        if (node.children) queue.push(...node.children)
    }
}

const tree = {
    value: 1,
    children: [
        {
            value: 2,
            children: [
                {
                    value: 3,
                    children: [{ value: 5 }, { value: 6 }, { value: 7 }]
                },
                {
                    value: 4
                }
            ]
        }
    ]
}

bfsWalk(tree)