Binary Tree Preorder Traversal

 
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

/*Method 1
    vector preorderTraversal(TreeNode *root) {
        vector output;
        if (!root) return output;
        
       stack st;
       st.push(root);
       while(!st.empty())
       {
           root = st.top();
           st.pop();
           output.push_back(root->val);
           if (root->right)
               st.push(root->right);
           if (root->left)
               st.push(root->left); 
       }
       
       return output;
    }
    */
    
    /*
    //Method 2
    vector preorderTraversal(TreeNode *root) {
       vector output;
       stack st;
       while(!st.empty() || root)
       {
           if (!root)
           {
              root = st.top();
              st.pop();
              root=root->right; 
           }
           else 
           {
               output.push_back(root->val);
               st.push(root);
               root = root->left; 
           }
       }
       
       return output;
    }
    */
    
     // Simple coder's solution
    vector preorderTraversal(TreeNode *root) {
       vector output;
       stack st;
     
       pushLeft(root, st, output);
       while (!st.empty()) {
            root = st.top();
            st.pop();
            pushLeft(root->right, st, output);
        }

       return output;
    }
    
    void pushLeft(TreeNode *root, stack &st, vector & output) {
       while(root) {
           output.push_back(root->val);
           st.push(root);
           root = root->left;
       }
   }
};