On this page

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 1
2 / \
3 2 3
4 / \ \
5 4 5 6

Recursion 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

  1. If the tree is empty, return an empty list.
  2. Push the root onto the stack.
  3. 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

Time: O(n)

Each node is pushed once and popped once.

Space: O(h)

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).

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch
"To avoid recursion I use my own stack. I push the root, and in a loop I pop a node, add its value, then push its right child and then its left child. I push right first so that the left child ends up on top and is processed first, which gives root, left, right. Each node is pushed and popped once, so time is O of n, and the stack holds at most the pending right children along one path, so space is O of h."
Next TopicIterative Inorder Traversal