Iterative Preorder Traversal
Do the preorder traversal (Root, Left, Right) of a binary tree without recursion. Return the node values as a list.
This is the iterative version of Binary Tree Preorder Traversal (LeetCode 144). It is a common follow-up: "Recursive is trivial, can you do it iteratively?"
Intuition
Every example below uses this tree:
1 12 / \3 2 34 / \ \5 4 5 6Recursion works because the call stack remembers where to come back to. We can do the same job with our own stack.
Preorder processes a node, then its left subtree entirely, then the right subtree. So after visiting a node, the right child has to wait while the left subtree is handled. A stack gives exactly that: last in, first out.
The trick is the push order. Push the right child first and the left child second, so the left child sits on top and is popped first.
Approach: Explicit Stack
- If the tree is empty, return an empty list.
- Push the root onto the stack.
- While the stack is not empty:
- Pop the top node and add its value to the answer.
- If it has a right child, push it.
- If it has a left child, push it.
Dry run on the sample tree:
- Stack
[1]. Pop 1, answer[1], push 3 then 2. Stack[3, 2]. - Pop 2, answer
[1, 2], push 5 then 4. Stack[3, 5, 4]. - Pop 4, answer
[1, 2, 4]. No children. - Pop 5, answer
[1, 2, 4, 5]. - Pop 3, answer
[1, 2, 4, 5, 3], push 6. Pop 6, answer[1, 2, 4, 5, 3, 6].
Code
class Solution {public:vector<int> preorderTraversal(TreeNode* root) {vector<int> ans;if (root == nullptr) return ans;stack<TreeNode*> st;st.push(root);while (!st.empty()) {TreeNode* node = st.top();st.pop();ans.push_back(node->val);if (node->right != nullptr) st.push(node->right);if (node->left != nullptr) st.push(node->left);}return ans;}};
Complexity
Each node is pushed once and popped once.
The stack never holds more than the pending right siblings along one root-to-leaf path, so it is O(h) in height. In the worst case that is O(n).