#include <iostream>

#include <vector>

#include <algorithm>

#include <stack>

using namespace std;

struct TreeNode {

    int val;

    TreeNode *left;

    TreeNode *right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

};

class Solution1 {

public:

    int maxDepth(TreeNode *root) {

        stack< TreeNode *> tovisit;

        stack< int> depth;

        int prof;

        int maxp = -1;

        tovisit.push(root);

        depth.push(0);

        while ( ! tovisit.empty()){

            // visite node

            TreeNode * pn = tovisit.top();

            tovisit.pop();

            prof = depth.top();

            depth.pop();

            printf("node %d prof %d --> ",pn->val, prof);

            if (prof > maxp)

                maxp = prof;

            // next node

            if (pn->right != nullptr){

                tovisit.push(pn->right);

                depth.push(prof+1);

            };

            if (pn->left != nullptr){

                tovisit.push(pn->left);

                depth.push(prof+1);

            };

        };

        return maxp;   

    };

};

class Solution2 {

public:

    int maxDepth(TreeNode *root) {

        if (root == nullptr){

            return -1;

        }else{

            return max( maxDepth(root->left)+1, maxDepth(root->right)+1 );

        }

    };

};

int main(){

    TreeNode * pn1 = new TreeNode(1);

    TreeNode * pn2 = new TreeNode(2);

    TreeNode * pn3 = new TreeNode(3);

    TreeNode * pn4 = new TreeNode(4); 

    TreeNode * pn5 = new TreeNode(5);

    TreeNode * pn6 = new TreeNode(6);

    TreeNode * pn7 = new TreeNode(7);

    TreeNode * pn8 = new TreeNode(8);

    pn1->left = pn2;

    pn1->right = pn3;

    pn2->left = pn4;

    pn2->right = pn5;

    pn3->left = pn6;

    pn3->right = pn7;

    pn4->left = pn8;

    Solution1 solution1;

    printf("Solution 1 stack: %d \n", solution1.maxDepth(pn1));

    Solution2 solution2;

    printf("Solution 2 recursion : %d \n", solution2.maxDepth(pn1));

    return 0;

}