Binary Tree Preorder Traversal

easy tree dfs stack

Problem

Return the preorder (root, left, right) traversal of a binary tree's node values.

Inputroot = [1, null, 2, 3]

Output[1, 2, 3]

Emit 1 (root), descend right to 2 (no left subtree), then visit 3.

level-order (use "null" for missing)

def preorder_traversal(root):
    if not root: return []
    out, stack = [], [root]
    while stack:
        n = stack.pop()
        out.append(n.val)
        if n.right: stack.append(n.right)
        if n.left:  stack.append(n.left)
    return out

function preorderTraversal(root) {
  if (!root) return [];
  const out = [], stack = [root];
  while (stack.length) {
    const n = stack.pop();
    out.push(n.val);
    if (n.right) stack.push(n.right);
    if (n.left) stack.push(n.left);
  }
  return out;
}

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        if (root == null) return out;
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode n = stack.pop();
            out.add(n.val);
            if (n.right != null) stack.push(n.right);
            if (n.left != null) stack.push(n.left);
        }
        return out;
    }
}

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> out;
    if (!root) return out;
    stack<TreeNode*> st; st.push(root);
    while (!st.empty()) {
        auto* n = st.top(); st.pop();
        out.push_back(n->val);
        if (n->right) st.push(n->right);
        if (n->left) st.push(n->left);
    }
    return out;
}

Explanation

Preorder means root, left, right. We can do this iteratively with an explicit stack instead of recursion, which avoids deep call stacks on tall trees.

We push the root, then loop: pop a node, emit its value, and push its children. The key detail is the order of pushing — we push the right child first and the left child second. Since a stack is last-in-first-out, the left child gets popped (and processed) before the right, which is exactly what preorder needs.

The value is appended to out the moment a node is popped, so the root is always recorded before its descendants. No reversing or extra bookkeeping is needed.

Example: tree [1, null, 2, 3]. Pop 1, emit 1, push its right child 2. Pop 2, emit 2, push its left child 3. Pop 3, emit 3. The output is [1, 2, 3].

Every node enters and leaves the stack exactly once, so the traversal is O(n) time with O(h) stack space.

Time: O(n) Space: O(h)