Binary Tree Preorder Traversal

Problem

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

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

Constraints

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Solution

The problem Binary Tree Preorder Traversal can be solved iteratively using a stack to store nodes. By traversing through the nodes and pushing right node and left node in order to the stack, it can be guaranteed that root node gets processed first, then left node, and finally right node, thus turning the process into a preorder traversal.

Implementation

typedef stack<TreeNode *> Stack;

/**
 * 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) {}
 * };
 */
class Solution
{
  public:
    vector<int> preorderTraversal(TreeNode *root)
    {
        Stack roots;
        roots.push(root);

        vector<int> ret;
        while (!roots.empty())
        {
            root = roots.top();
            roots.pop();
            if (root == NULL)
                continue;

            ret.push_back(root->val);
            roots.push(root->right);
            roots.push(root->left);
        }

        return ret;
    }
};