2. Pre-Order

Root --> left --> right

// Recursive
private void TraverseTree (Node root) {
	System.out.println(root.data);
	TraverseTree(Node.left);
	TraverseTree(Node.right);
}

// Iterative
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> pre;
    if(root == nullptr) return pre;
    stack<TreeNode*> st; 
    st.push(root);
	while(!st.empty()){
        TreeNode* it = st.top();
        st.pop();
        pre.push_back(it->val);
        if(it->right != nullptr) st.push(it->right);
        if(it->left  != nullptr) st.push(it->left);
    }   
    return pre;
}

// Helper Function
void dfs(TreeNode* root, vector<int>& ans) {
    if (!root) return;
    ans.push_back(root->val);
    dfs(root->left, ans);
    dfs(root->right, ans);
}

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ans;
    dfs(root, ans);
    return ans;
}