I wrote the following recursive JS function that takes a single parameter node which is made of other nodes and modifies it by adding to each node its number of leaves (not only direct children) :

const addWidths = (node) => {
    const keys = Object.keys(node)
    for(const key of keys){
        addWidths(node[key])
    }
    if(keys.length > 0){
        node["width"] = Object.values(node).reduce((acc, cur) => acc   cur["width"], 0)
    }else{
        node["width"] = 1
    }
}

Here's an example of the node parameter :

const object = {
    "A": {
        "1": {},
        "2": {
            " ": {},
            "-": {}
        },
        "3": {}
    },
    "B": {
        "1": {}
    },
    "C": {},
    "D": {}
}

addWidth(object) would modify it and turn it into :

{
    "A": {
        "1": {
            "width": 1
        },
        "2": {
            " ": {
                "width": 1
            },
            "-": {
                "width": 1
            },
            "width": 2
        },
        "3": {
            "width": 1
        },
        "width": 4
    },
    "B": {
        "1": {
            "width": 1
        },
        "width": 1
    },
    "C": {
        "width": 1
    },
    "D": {
        "width": 1
    },
    "width":7
}

I need help to make my function iterative.

EDIT: Here's a drawing of the modified tree with the expected widths of each node :

CodePudding user response：

It looks like your intent is to only count leaves in the tree, not internal nodes.

Your recursive implementation can be written without recursion by using an explicit stack to mimic what the recursive implementation does:

const addWidths = (node) => {
    const stack = [[node, Object.values(node)]];
    while (stack.length) {
        const [node, nonvisited] = stack.at(-1);
        if (nonvisited.length == 0) {
            stack.pop();
            node.width = Object.values(node)
                        .reduce((sum, {width}) => sum   width, 0) || 1;
        } else {
            const child = nonvisited.pop();
            stack.push([child, Object.values(child)]);
        }
    }
}

const object = {
    "A": {
        "1": {},
        "2": {
            " ": {},
            "-": {}
        },
        "3": {}
    },
    "B": {
        "1": {}
    },
    "C": {},
    "D": {}
}
addWidths(object);
console.log(object);

Here is a variant that has a more flat stack structure:

const addWidths = (node) => {
    const stack = [node];
    while (stack.length) {
        const node = stack.pop();
        const children = Object.values(node);
        if (children.length && !children[0].width) {
            stack.push(node, ...children);
        } else {
            node.width = children.reduce((sum, {width}) => sum   width, 0) || 1;
        }
    }
}

const object = {
    "A": {
        "1": {},
        "2": {
            " ": {},
            "-": {}
        },
        "3": {}
    },
    "B": {
        "1": {}
    },
    "C": {},
    "D": {}
}
addWidths(object);
console.log(object);

CodePudding user response：

First of all, you could take a single loop iteration for every object in standard recursive approach.

const addWidths = node => {
    let width = 0;
    for (const key in node) width  = addWidths(node[key]);
    node.width = width || 1;
    return node.width;
};

const object = { A: { 1: {}, 2: { " ": {}, "-": {} },  3: {} }, B: { 1: {} }, C: {}, D: {} } ;

addWidths(object);
console.log(object);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Now the converted approach by using an iterative approach with a stack, where the node and the parent nodes are stored.

const addWidths = node => {
    const stack = [[node, []]];
  
    while (stack.length) {
        const [node, parents] = stack.pop();
        let hasChildren = false;
        for (const key in node)  {
            stack.push([node[key], [...parents, node]]);
            hasChildren = true;
        }
        if (!hasChildren) {
            for (const parent of parents) parent.width = (parent.width || 0)   1;
            node.width = 1;
        }
    }
}

const object = { A: { 1: {}, 2: { " ": {}, "-": {} },  3: {} }, B: { 1: {} }, C: {}, D: {} } ;

addWidths(object);
console.log(object);

.as-console-wrapper { max-height: 100% !important; top: 0; }