#include <bits/stdc++.h>

// Prepare > Data Structures > Trees > Tree: Height of a Binary Tree

// The height of a binary tree is the number of edges between the
// tree's root and its furthest leaf. For example, the following
// binary tree is of height 3:

/*              3
               / \
              2   5
             /    |\
            1     4 6
                     \
                      7
*/

using namespace std;

enum class TraversalType : int {PreOrder = 0, PostOrder = 1};

class Node {
public:
    
    int data;
    Node *left;
    Node *right;
    Node(int d) {
        data = d;
        left = nullptr;
        right = nullptr;
    }
};

class Solution {
public:
    Node* insert(Node* root, int data) {
        if(root == NULL)
        {
            return new Node(data);
        }
        else
        {
            Node* cur;
            if(data <= root->data) {
                cur = insert(root->left, data);
                root->left = cur;
            } else {
                cur = insert(root->right, data);
                root->right = cur;
            }

            return root;
        }
    }

    void free_tree(Node* root) {
        // Deallocates memory corresponding to every node in the tree.
        Node* temp = root;
        if (temp == nullptr)
            return;
        free_tree(temp->left);
        free_tree(temp->right);
        if (!temp->left && !temp->right) {
            free(temp);
            temp = nullptr;
            return;
        }
    }
    
    int height(Node *root) {
        if (root == NULL)
            return -1;
        else
        {
            int left = height(root->left);
            int right = height(root->right);
            return 1 + max(left, right);
        }
    }

    template <typename T>
    void print(Node* node, T traversalType)
    {
        if (node == NULL)
            return;
        
        if (traversalType == TraversalType::PreOrder)
        {            
            cout << node->data << " ";
            print<T>(node->left, traversalType);
            print<T>(node->right, traversalType);
        }
        if (traversalType == TraversalType::PostOrder)
        {
            print<T>(node->left, traversalType);
            print<T>(node->right, traversalType);
            cout << node->data << " ";
        }

    }

}; //End of Solution

int main()
{    
    multimap<int, tuple<vector<int>,int>> testCases = {
      // n  data              height
      // -  -------------     ------  
      {  7, {{3,5,2,1,4,6,7}, 3     }},
      {  1, {{15},            0     }},
      {  5, {{3,1,7,5,4},     3     }},
    };

    for (auto& tc: testCases )
    {    
        cout << "n: " << tc.first << " data: ";
        for (auto& y: get<0>(tc.second))
        {
            cout << y << " ";
        }
        cout << endl;

        Solution myTree;
        Node* root = nullptr;
            
        for (auto& data: get<0>(tc.second))
        {
            //cout << "insert " << data << endl;
            root = myTree.insert(root, data);
            //cout << "root: " << hex << root << dec << endl;
        }

        cout << "print " << setw(15) << "PreOrder: ";
        myTree.print(root, TraversalType::PreOrder);
        cout << endl;

        cout << "print " << setw(15) << "PostOrder: ";
        myTree.print(root, TraversalType::PostOrder);
        cout << endl;
        
        cout << "expected: " << get<1>(tc.second)
        << " actual: " << myTree.height(root) << endl;

        cout << "-------------------------" << endl;
        
        myTree.free_tree(root);
    }
    
    return 0;
}