/

* Author: Raghavendra Mallela

*/

* LeetCode 144: Binary Tree PreOrder Traversal

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

* Example 1:

* Input: root = [1,null,2,3]

* Output: [1,2,3]

* Example 2:

* Input: root = []

* Output: []

* Example 3:

* Input: root = [1]

* Output: [1]

* Example 4:

* Input: root = [1,2]

* Output: [1,2]

* Example 5:

* Input: root = [1,null,2]

* Output: [1,2]

* Constraints:

* The number of nodes in the tree is in the range [0, 100].

* -100 <= Node.val <= 100

* Follow up: Recursive solution is trivial, could you do it iteratively?

*/

* PreOrder Traversal is Left, Root, Right

* Recursive Approach where we traverse through the left subtree and

* once child is reached, print the current node and traverse to right

* Iterative approach is to use a stack.

*/

// Recursive approach

void preorder_r(TreeNode* root, vector<int>& res) {

// Check if the root is NULL

if (root == NULL) {

return;

}

// Push the root value to result

res.push_back(root->val);

// Traverse the left subtree

preorder_r(root->left, res);

// Traverse the right subtree

preorder_r(root->right, res);

return;

// Iterative approach

void preorder_i(TreeNode* root, vector<int>& res) {

// Check if the root is NULL

if (root == NULL) {

return;

}

// stack to store the nodes

stack<TreeNode*> st;

// Push the root node to stack

st.push(root);

// Loop while the stack is not empty

while (!st.empty()) {

// Retreive the top node from stack

TreeNode* node = st.top();

st.pop();

// Push the current node value to result

res.push_back(node->val);

// Push the right node first to stack

if (node->right) {

st.push(node->right);

}

// Push the left node to stack

if (node->left) {

st.push(node->left);

}

}

return;

vector<int> preorderTraversal(TreeNode* root) {

// vector to store the result

vector<int> res;

//preorder_r(root, res);

preorder_i(root, res);

return res;