Why does lifting the resultant array make the recursion work as expected?

by

Consider the following tree.

Example Tree

It’s represented by the following data structure.

const Node = (name, value, children) => ({ name, value, children });

const tree = Node("A", 4, [
    Node("B", 7, [
        Node("C", 9, [])
    ]),
    Node("D", 11, [
        Node("E", 9, [])
    ]),
    Node("F", 55, []),
    Node("G", 65, [
        Node("H", 21, []),
        Node("I", 23, [])
    ])
]);

Now, I want to get an array of all the values in the tree greater than a certain value. Here’s what I tried.

const Node = (name, value, children) => ({ name, value, children });

const tree = Node("A", 4, [
    Node("B", 7, [
        Node("C", 9, [])
    ]),
    Node("D", 11, [
        Node("E", 9, [])
    ]),
    Node("F", 55, []),
    Node("G", 65, [
        Node("H", 21, []),
        Node("I", 23, [])
    ])
]);

const result = findHigherInNode(tree, 20);

console.log(result);

function findHigherInNode(node, num) {
    console.log(node.name);
    const isGreater = [];
    if (node.value > num) {
        isGreater.push(node.value);
    }
    for (let i = 0; i < node.children.length; i++) {
        findHigherInNode(node.children[i], num);
    }
    return isGreater;
}

Note that although I’m traversing the entire tree, yet I’m not getting the correct result.

However, if I move the recursion into a local recurse function while keeping the isGreater array in the same scope then it works.

const Node = (name, value, children) => ({ name, value, children });

const tree = Node("A", 4, [
    Node("B", 7, [
        Node("C", 9, [])
    ]),
    Node("D", 11, [
        Node("E", 9, [])
    ]),
    Node("F", 55, []),
    Node("G", 65, [
        Node("H", 21, []),
        Node("I", 23, [])
    ])
]);

const result = findHigherInNode(tree, 20);

console.log(result);

function findHigherInNode(node, num) {
    const isGreater = [];
    function recurse(node, num) {
        if (node.value > num) {
            isGreater.push(node.value);
        }
        for (let i = 0; i < node.children.length; i++) {
            recurse(node.children[i], num);
        }
    }
    recurse(node, num);
    return isGreater;
}

Why does my first code snippet produce the wrong result? Why does my second code snippet produce the right result? The only difference between them is that the isGreater array is lifted to a higher scope in the second code snippet.

20 thoughts on “Why does lifting the resultant array make the recursion work as expected?”

Leave a Comment