2.Pre-order Traversal

Pre means root at first.

Pre-order traversal is to visit the root first. Then traverse the left subtree. Finally, traverse the right subtree.

Preorder traversal is used to create a copy of the tree

Iterative Method using stack

Steps: 1. Print a node 2. Add the address to stack 2. Move to left subtree 3. Move to right subtree

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        
        vector<int> v;
        TreeNode *t = root;
        stack <TreeNode*> s;
        
        while(t!=NULL || !s.empty()){
            
            if(t!=NULL){
                v.push_back(t->val);
                s.push(t);
                t = t->left;
            }
            else{
                t = s.top();
                s.pop();
                t = t->right;
            }
            
        }
        return v;
        
    }
};

Recursive method

class Solution
{
public:
    vector<int> v;
    void preorder(TreeNode *t)
    {
        if (t == NULL){
            return;
        }
        v.push_back(t->val);
        preorder(t->left);
        preorder(t->right);
    }

    vector<int> preorderTraversal(TreeNode *root)
    {
        preorder(root);
        return v;
    }
};