(Template) Binary Tree Traversal

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	private:
	void preorderTraversal(TreeNode* root, vector<int>& answer) {
	if (!root) {
	return;
	}
	answer.push_back(root->val); // visit the root
	preorderTraversal(root->left, answer); // traverse left subtree
	preorderTraversal(root->right, answer); // traverse right subtree
	}
	void inorderTraversal(TreeNode* root, vector<int>& answer) {
	if (!root) {
	return;
	}
	inorderTraversal(root->left, answer); // traverse left subtree
	answer.push_back(root->val); // visit the root
	inorderTraversal(root->right, answer); // traverse right subtree
	}
	void postorderTraversal(TreeNode* root, vector<int>& answer) {
	if (!root) {
	return;
	}
	postorderTraversal(root->left, answer); // traverse left subtree
	postorderTraversal(root->right, answer); // traverse right subtree
	answer.push_back(root->val); // visit the root
	}
	// Iterative
	vector<int> preorderTraversal(TreeNode* root) {
	vector<int> answer;
	stack<TreeNode*> s;
	if (root) {
	s.push(root);
	}
	TreeNode* cur;
	while (!s.empty()) {
	cur = s.top();
	s.pop();
	answer.push_back(cur->val); // visit the root
	if (cur->right) {
	s.push(cur->right); // push right child to stack if it is not null
	}
	if (cur->left) {
	s.push(cur->left); // push left child to stack if it is not null
	}
	}
	return answer;
	}
	};

view raw Binary Tree Traversal.cpp hosted with ❤ by GitHub