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.

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

  1. Why does my first code snippet produce the wrong result?

    Because isGreater is a new binding, initialized to [] each time findHigherInNode is called

    Why does my second code snippet produce the right result?

    Because isGreater is initialized once after findHigherInNode is called, and recurse does not create a new binding for each subsequent call

    Why am I experiencing this kind of problem?

    Because you are not using generators! Generators make this kind of problem disappear –

    function* inorder (t)
{ yield t.value
  for (const c of t.children)
    yield *inorder(c)
}

const tree =
  {name: 'A',value: 21,children: [{name: 'B', value: 7,children: [{name: 'C', value: 9, children: []}]},{name: 'D', value: 11,children: [{name: 'E', value: 9, children: []}]},{name: 'F', value: 55, children: []},{name: 'G', value: 65,children: [{name: 'H', value: 21, children: []},{name: 'I', value: 33, children: []}]}]}
  
for (const v of inorder(tree))
  if (v > 20)
    console.log(v)
    21
55
65
21
33

    However, it would probably be smarter to yield the entire node, allowing the caller of the generator to choose which data is relevant to select from the traversal

    function* inorder (t)
{ yield t                       // <- yield entire node
  for (const c of t.children)
    yield *inorder(c)
}

const tree =
  {name: 'A',value: 21,children: [{name: 'B', value: 7,children: [{name: 'C', value: 9, children: []}]},{name: 'D', value: 11,children: [{name: 'E', value: 9, children: []}]},{name: 'F', value: 55, children: []},{name: 'G', value: 65,children: [{name: 'H', value: 21, children: []},{name: 'I', value: 33, children: []}]}]}

for (const node of inorder(tree))
  if (node.value > 20)                    // <- entire node accessible here
    console.log(node.name, node.value)
    A 21
F 55
G 65
H 21
I 33

    But is it possible without generators

    OK, no one is forcing your hand.

    function inorder (t)
{
  return [t, ...t.children.flatMap(inorder)]
}

const tree =
  {name: 'A',value: 21,children: [{name: 'B', value: 7,children: [{name: 'C', value: 9, children: []}]},{name: 'D', value: 11,children: [{name: 'E', value: 9, children: []}]},{name: 'F', value: 55, children: []},{name: 'G', value: 65,children: [{name: 'H', value: 21, children: []},{name: 'I', value: 33, children: []}]}]}
  
for (const node of inorder(tree))
  if (node.value > 20)
    console.log(node.name, node.value)
    A 21
F 55
G 65
H 21
I 33
    Reply

Leave a Comment