#include <bits/stdc++.h>

using namespace std;

//***********************************************************************
// HackerRank Prepare > Data Structures > Trees: Tree Postorder Traversal
//***********************************************************************
	
class Node {
public:
    int data;
    Node *left;
    Node *right;
    Node(int d) {
        data = d;
        left = NULL;
        right = NULL;
    }
};

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 postOrder(Node *root) {
        if (root == nullptr)
            return;

        postOrder(root->left);
        postOrder(root->right);
        cout << root->data << " ";
    }
}; //End of Solution

int main()
{
    /****************
     1 
      \
       2
        \
         5
        / \
       3   6
        \
         4
    *****************/
    vector<tuple<int,vector<int>,vector<int>>> testCases = {
        {{6, {1,2,5,3,6,4},{4,3,6,5,2,1}}},        
    };
    
    for (auto& tc: testCases)
    {
        Solution myTree;
        Node* root = nullptr;
        
        for (auto& data: get<1>(tc))
        {
            root = myTree.insert(root, data);
        }
        cout << "  result: ";        
        myTree.postOrder(root);
        cout << endl;
        cout << "expected: "; for (auto i: get<2>(tc)) {cout << i << " ";} cout << endl;
    }
    
    return 0;
}