Binary Tree Preorder Traversal

Given the root of a binary tree, return the preorder traversal of its nodes' values — visit the node first, then the left subtree, then the right subtree.

The tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

Preorder means the node first, then the left subtree, then the right subtree.

Recursively that's three lines; iteratively use an explicit stack.

For the iterative version, push the right child before the left so the left comes off the stack first.

Common doubts

You emit each node before its children, so a rebuilder can create the node and then attach the subtrees it reads next.

A stack is last-in-first-out; pushing right first leaves the left child on top, so it's processed next — matching node-left-right order.

O(height) for the recursion/stack — O(log n) balanced, O(n) for a degenerate tree.

Interview follow-ups

· What an interviewer asks next.

A preorder walk with explicit null markers uniquely encodes a binary tree, which is the basis of many serialize/deserialize solutions.

Not from values alone unless you also record nulls or have a second traversal (e.g. preorder + inorder) to locate subtree boundaries.

Fun facts

Preorder traversal is exactly how you'd read a nested outline: the heading first, then its sub-points.
Preorder + inorder (or postorder + inorder) together uniquely determine a binary tree.

Asked at

AmazonMicrosoftGoogle

Frequently Sometimes Occasionally

Example 1

Input: root = [1, null, 2, 3]
Output: [1, 2, 3]
Record 1, then its left subtree (empty), then its right subtree yielding 2 then 3.

Example 2

Input: root = []
Output: []
An empty tree has no nodes.

Constraints

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

Preorder means node, left, right — record a node the moment you reach it, then descend. The recursive version is a direct transcription; the iterative version uses a stack, pushing the right child before the left so the left comes off first.

Prerequisites

Before you start

· Concepts used directly in the solution.

Binary tree. Nodes with a value and up to two children (left, right).

Stack (LIFO). Last-in-first-out — the key to ordering children in the iterative version.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The order

“What is preorder exactly?”

The current node, then its left subtree, then its right subtree.

“Where is preorder used?”

Copying/serializing a tree — you emit a node before its children, so rebuilding is straightforward.

The ideal opening — say it like this

Preorder is node, left, right, so I record the node first, then recurse left, then recurse right.

Iteratively I use a stack and push the right child before the left, so the left is processed first.

Understand the problem

Worked example — tree [1, null, 2, 3] (1 with right child 2, whose left child is 3)

        1
         \
          2
         /
        3
preorder: 1 -> left of 1 (none) -> right subtree of 1
          in that subtree: 2 -> 3
result: [1, 2, 3]

Key observations

1Aha

Preorder is node, left, right

Record on arrival, before descending — that's what distinguishes it from inorder and postorder.

2Aha

Push right before left

A stack is LIFO, so to pop the left child first you must push it last — push right, then left.

3Aha

Linear time and height space

Every node is visited once (O(n)); the stack holds at most O(height) nodes.

Brute force vs optimal

	Iterative (explicit stack)	Recursive
Idea	Pop, record, push right then left	record; dfs(left); dfs(right)
Time	O(n)	O(n)
Space	O(height)	O(height)

Both are O(n); the recursive form is the clearest, the iterative form avoids the call stack. Full code is in the Approaches selector below.

Summary

Key takeaway

Preorder = node, left, right. Record the node on arrival, then recurse left and right — or use a stack, pushing the right child before the left. O(n) time, O(height) space.

preorder(node):
    if node is null: return
    visit(node)
    preorder(node.left)
    preorder(node.right)