144 Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.

For example: Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3]. Note: Recursive solution is trivial, could you do it iteratively?

• A stack will naturally preserve the pre-order, in a very similiar way that level order used a queue. A stack will prioritize elements that come from the left FIRST, before the right.

// iteratively

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> pre_order;
    if (!root) return pre_order;
    stack<TreeNode*> s;
    s.push(root);

    while (!s.empty()) {
        TreeNode *temp = s.top();
        pre_order.push_back(temp->val);
        s.pop();

        if (temp->right) s.push(temp->right);
        if (temp->left) s.push(temp->left);
    }

    return pre_order;
}

// recursively

// LDR
vector<int> pre_order;
vector<int> preorderTraversal(TreeNode* root) {
    if (root != nullptr) {
        pre_order.push_back(root->val);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
    return pre_order;
}