C++ getting lowest level of a tree

Question

I need to know how many leafs have a tree but with some conditions.

• All the children or leafs, will be always on the same level, but it can be the level 1,2,3,4,5 ... I don't know which one will be. So you can't count grandhildren + grandgrandchildren ... they will be at the same level and will be the lower of them, in that case: grandgrandchildren.
• There must be a node without leafs, but if it is not the lowest level of leafs, it doesn't have to count as leaf.

I will try to explain myself with some examples. Imagine you have this tree:

 A
 |- B
 |  |- B1
 |  |- B2                 Number of 'leafs' = 2 (B1 and B2). C doesn't count as it is in an 
 |                                                           upper level)
 |- C

Another example:

 A
 |- B
 |  |- B1
 |  |- B2                 Number of 'leafs' = 3 (B1,B2,D1)
 |
 |- C
 |- D
    |-D1

Another example:

 A
 |- B
 |  |- B1
 |  |   |-B11
 |  |- B2                 Number of 'leafs' = 1 (B11). D1 is not a leaf. It is a 'node' as 
 |                                    leafs in this case are in level 4 (counting A as 1)
 |- C
 |- D
    |-D1

I'm working with C++ and Qt with something similar to QTreeWidgetItem so I have an object (let's call it myTree and I can ask something like: myTree->childCount() so in the first example, if I call it, it will say 2 (B and C) and for each one I can repeat the operation.

I was trying to count everything that gives me childcount() but then, it gaves me 4 (B,C,B1 and B2) instead of 2 (B1,B2) which is what i want...Here I put what I was trying:

 int grandchild = 0;
   for (int i = 0; i < myTree->childCount( ); ++i)
   {
        Obj* child = myTree->child( i ); //Get the children. First time will be B and C
        if (child)
        {
          grandchild += p_child->childCount( ); // Here I wanted to get a total, for first example, I will get 3 which is not what I want 
        }
    }

Thank you in advance.

Answer 1

For recursive functions, you start with the assumption that the function, when operating on a node, will return all relevant information about that node. Each node then only needs to inspect its children and itself to decide what to return to the level above it.

If the node has no children, then the result is trivial: this node has one max depth node at a depth of 0 (itself).

Otherwise, the max depth is equal to the largest max depth among its children + 1, and the count is equal to the sum of the counts of all children that share the largest max depth.

#include <utility>
#include <vector>

struct node_type {
    std::vector<node_type*> children;
};

// returns the max depth between the node and all of its children
// along with the number of nodes at that depth
std::pair<int, int> max_depth_count(const node_type& node) {
    int depth = 0; // itself
    int count = 1; // itself

    for (const auto c : node.children) {
        auto [child_depth, child_count] = max_depth_count(*c);
        child_depth++;

        if (child_depth > depth) {
            depth = child_depth;
            count = child_count;
        }
        else if (child_depth == depth) {
            count += child_count;
        }
    }

    return {depth, count};
}