// Example program
#include <iostream>
#include <string>
#include <vector>
#include <stack>

using std::vector;
using std::stack;
using std::cout;

//Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
    ~TreeNode() {
        cout << "Destroying Node[val=" << val << "]\n";
    }
};

struct Tree {
    // treeVals should be a valid array-representation of a binary tree
    Tree(const vector<int> treeVals) {
        if (treeVals.empty()) return;

        for (auto val : treeVals) tree.push_back(new TreeNode(val));

        // Set up the tree structure
        for (unsigned int i = 1; i < treeVals.size(); ++i) {
            if (i % 2 == 1) {
                tree[(i - 1) / 2]->left = tree[i];
            }
            else {
                tree[(i - 1) / 2]->right = tree[i];
            }
        }
    }
    ~Tree() {
        for (auto tn : tree) free(tn); // Edited: This should be "delete tn", not free()!
    }
private:
    vector<TreeNode*> tree;
};

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if (!root) return vector<int>{};

        vector<int> visited;
        stack<TreeNode*> stk; // stk: Stores nodes to be visited; top node is the next node to visit
        stk.push(root); // Initialize the stack with root node

        while (!stk.empty()) {
            auto node = stk.top();
            visited.push_back(node->val); // "Visit" the node
            stk.pop();

            // If children nodes exists, mark them for visitation 
            if (node->right) stk.push(node->right);
            if (node->left) stk.push(node->left); // Left child must be top element for preorder traversal. 
        }
        return visited;
    }
};


int main()
{
    Tree t1(vector<int>{100, 19, 36, 17, 3, 25, 1, 2, 7});
    return 0;
}