Binary Tree Preorder Traversal

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

Solution: Using Stack

We can create a stack to store the child nodes. We push the root node to the stack first. Then each time, we process the top node of the stack first. We process left node before right node, so first we push right node to the stack. Then we push left node to the stack. (FIFO)

vector<int> preorderTraversal(TreeNode* root) {
    if (!root) return {};

    vector<int> result;
    stack<TreeNode*> stack;        
    stack.push(root);
    while(!stack.empty()) {
        TreeNode* node = stack.top();
        result.push_back(node->val);
        stack.pop();

        if(node->right) stack.push(node->right);
        if(node->left)  stack.push(node->left);
    }

    return result;
}

Solution: Recursive

void preorderTraversalUtil(TreeNode* root, vector<int> &result) {
    if(root == NULL) return;
    result.push_back(root->val);
    preorderTraversalUtil(root->left, result);
    preorderTraversalUtil(root->right, result);
}

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> result;
    preorderTraversalUtil(root, result);
    return result;
}