# Binary Tree Preorder/Inorder/Postorder/Levelorder Traversal Template (Recursive/Iteration)

###### tags: `algorithm template` `c++` `Binary Tree`

TreeNode Define

/**
 * 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) {}
 * };
 */

## Recursive
#### Preorder

class Solution {
public:
    vector<int> res;

    void traversal(TreeNode *cur) {
        if (cur == nullptr) {
            return;
        }
        res.push_back(cur->val);  // middle
        traversal(cur->left);     // left
        traversal(cur->right);    // right
    }

    vector<int> preorderTraversal(TreeNode* root) {
        traversal(root);
        return res;
    }
};

#### Inorder

class Solution {
public:
    vector<int> res;

    void traversal(TreeNode *cur) {
        if (cur == nullptr) {
            return;
        }
        traversal(cur->left);     // left
        res.push_back(cur->val);  // middle
        traversal(cur->right);    // right
    }

    vector<int> inorderTraversal(TreeNode* root) {
        traversal(root);
        return res;
    }
};

class Solution {
public:
    vector<int> res;
    TreeNode *pre;

    void traversal(TreeNode *cur) {
        if (cur == nullptr) {
            return;
        }
        traversal(cur->left);
        if (pre != nullptr) {
            res.push_back(pre->val);
        }
        pre = cur;
        traversal(cur->right);
    }

    vector<int> inorderTraversal(TreeNode* root) {
        traversal(root);
        if (pre != nullptr) {
            res.push_back(pre->val);
        }
        return res;
    }
};

#### Postorder

class Solution {
public:
    vector<int> res;

    void traversal(TreeNode *cur) {
        if (cur == nullptr) {
            return;
        }
        traversal(cur->left);     // left
        traversal(cur->right);    // right
        res.push_back(cur->val);  // middle
    }

    vector<int> postorderTraversal(TreeNode* root) {
        traversal(root);
        return res;
    }
};

Preorder / Inorder / Postorder的差別在只有三行(middle, left, right的順序).
#### Levelorder

class Solution {
public:
    vector<vector<int>> res;

    void traversal(TreeNode *cur, int level) {
        if (cur == nullptr) {
            return;
        }
        if (res.size() == level) {
            res.push_back(vector<int>());
        }
        res[level].push_back(cur->val);
        traversal(cur->left, level + 1);
        traversal(cur->right, level + 1);
    }

    vector<vector<int>> levelOrder(TreeNode* root) {
        traversal(root, 0);
        return res;
    }
};

## Iteration
#### Preorder

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode *> st;
        vector<int> res;

        if (root != nullptr) {
            st.push(root);
        }
        while (!st.empty()) {
            TreeNode *node = st.top();
            st.pop();

            res.push_back(node->val);
            if (node->right) {
                st.push(node->right);
            }
            if (node->left) {
                st.push(node->left);
            }
        }
        return res;
    }
};

#### Inorder

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        TreeNode *cur = root;
        stack<TreeNode *> st;
        vector<int> res;

        while (!st.empty() || cur != nullptr) {
            if (cur != nullptr) {
                st.push(cur);
                cur = cur->left;
            } else {
                cur = st.top();
                st.pop();

                res.push_back(cur->val);
                cur = cur->right;
            }
        }
        return res;
    }
};

use `pre` pointer version.

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        TreeNode *cur = root;
        TreeNode *pre = nullptr;
        stack<TreeNode *> st;
        vector<int> res;

        while (!st.empty() || cur != nullptr) {
            if (cur != nullptr) {
                st.push(cur);
                cur = cur->left;
            } else {
                cur = st.top();
                st.pop();

                res.push_back(cur->val);
                pre = cur;
                cur = cur->right;
            }
        }
        return res;
    }
};

#### Postorder
基本上跟 Preorder 一樣, 最後多了reverse而已.

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode *> st;
        vector<int> res;

        if (root != nullptr) {
            st.push(root);
        }
        while (!st.empty()) {
            TreeNode *node = st.top();
            st.pop();
            res.push_back(node->val);
            if (node->right != nullptr) {
                st.push(node->right);
            }
            if (node->left != nullptr) {
                st.push(node->left);
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

#### Levelorder

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> q;

        if (root != nullptr) {
            q.push(root);
        }
        while (!q.empty()) {
            int size = q.size();
            vector<int> level;

            for (int i = 0; i < size; i++) {
                TreeNode *node = q.front();
                q.pop();
                level.push_back(node->val);
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
            res.push_back(level);
        }
        return res;
    }
};

## Related Topics
### [LC 144. Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal/)
### [LC 94. Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/)
### [LC 145. Binary Tree Postorder Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/)
### [LC 102. Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/)

>### Complexity
>n = number of tree's nodes
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Preorder | O(n) | O(n) |
>| Inorder | O(n) | O(n) |
>| Postorder | O(n) | O(n) |
>| Levelorder | O(n) | O(n) |

## Note
[iteration reference](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E7%BB%9F%E4%B8%80%E8%BF%AD%E4%BB%A3%E6%B3%95.md)
[recursive reference](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.md)