I wrote a template class named "Tree<T>" in C++ which attributes are :
- T data
- std::vector<Tree*> sons;

I wrote the basic methods consisting of writing and reading in those two attributes. Now, I'm writing methods that return the min and max depth.

I have no compilation problems but when I test these methods on an example, I get false values. Here's the code for the minDepth and maxDepth methods (the other methods have names that make clear what they do) :

    int numberOfLevels() //we assume that this methode will be called on an initialized node
        if (nbSons()==0) return 1;
        std::vector<int> v;
        for (int i=0;i<nbSons();i++) v.push_back(sons[i]->numberOfLevels());
        return 1+max_v(v);

    int maxDepth()
        return numberOfLevels()-1;

    int minDepth()
        if (nbSons()==0) return 0;
        std::vector<int> v;
        for (int i=0;i<nbSons();i++) v.push_back(sons[i]->minDepth());
        return 1+min_v(v);

In the main, I define the tree shown in the attached picture, then I call min and max depth methods. Here's the main :

Tree<int>* root=new Tree<int>(1);
    root->addAsLastSon(new Tree<int>(2)); // node 0
    root->addAsLastSon(new Tree<int>(6)); // node 1
    root->addAsLastSon(new Tree<int>(7)); // node 2
    // Sons of node 0
    (root->getSon(0))->addAsLastSon(new Tree<int>(3)); //node 00
    (root->getSon(0))->addAsLastSon(new Tree<int>(4)); //node 01
    // Son of node 01
    ((root->getSon(0))->getSon(1))->addAsLastSon(new Tree<int>(5));
    // Sons of node 2
    (root->getSon(2))->addAsLastSon(new Tree<int>(8)); //node 20
    // Sons of node 20
    ((root->getSon(2))->getSon(0))->addAsLastSon(new Tree<int>(9)); //node 200
    ((root->getSon(2))->getSon(0))->addAsLastSon(new Tree<int>(11));
    ((root->getSon(2))->getSon(0))->addAsLastSon(new Tree<int>(12));
    //Son of node 200
    (((root->getSon(2))->getSon(0))->getSon(0))->addAsLastSon(new Tree<int>(10));
    std::cout<<"Minimum depth : "<<root->minDepth()<<std::endl;
    std::cout<<"Maximum depth : "<<root->maxDepth()<<std::endl;

I obtain :

Minimum depth : 1
Maximum depth : 3 (instead of 4)

I can't figure out why.

This article has been dead for over six months. Start a new discussion instead.