Classical Recursion Solution of N-ary Tree

https://www.geeksforgeeks.org/diameter-n-ary-tree-using-bfs/

1. "Top-down" Solution

"Top-down" means that in each recursion level, we will visit the node first to come up with some values, and pass these values to its children when calling the function recursively.

A typical "top-down" recursion functiontop_down(root, params)works like this:

1. return specific value for null node
2. update the answer if needed                              // answer <-- params
3. for each child node root.children[k]:
4.      ans[k] = top_down(root.children[k], new_params[k])  // new_params <-- root.val, params
5. return the answer if needed                              // answer <-- all ans[k]

Maximum Depth of N-ary Tree (Top Down)

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
// top-down
class Solution {
    int ans = 1;
public:
    int maxDepth(Node* root) {
        if (root == nullptr) return 0;
        depth(root, 1);
        return ans;
    }

private:
    void depth(Node* root, int level) {
        if (root == nullptr) return;

        // leaf node
        if (root->children.size() == 0)
            ans = max(ans, level);

        for (auto child : root->children) {
            depth(child, level+1);
        }
    }
};

2. "Bottom-up" Solution

"Bottom-up" means that in each recursion level, we will firstly call the functions recursively for all the children nodes and then come up with the answer according to the return values and the value of the root node itself.

A typical "bottom-up" recursion function bottom_up(root)works like this:

1. return specific value for null node
2. for each child node root.children[k]:
3.      ans[k] = bottom_up(root.children[k])    // call function recursively for all children
4. return answer                                // answer <- root.val, all ans[k]

Maximum Depth of N-ary Tree (Bottom-up)

class Solution {
public:
    int maxDepth(Node* root) {
        if (root == nullptr) return 0;
        //leaf node
        if(root->children.size() == 0) return 1;

        int maximumDepth = 0;
        for(Node* child : root->children) {
            int subtreeDepth = maxDepth(child);
            if(subtreeDepth + 1 > maximumDepth) maximumDepth = subtreeDepth + 1;
        }
        return maximumDepth;
    }
};