LeetCode #144 Easy

Binary Tree Preorder Traversal

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

binary treedfsrecursion

Open on LeetCode ↗

02

Intuition

Preorder visits a node the moment it's discovered — record first, explore later. It's the order you'd photocopy a tree: root, then everything under the left child, then everything under the right.

How to spot this pattern

Node before children — the order in which you'd build a tree, which is why preorder plus inorder uniquely reconstructs one and why serialisation formats use it. The first element is always the root of the current subtree.

03

Approach

1

Visit before you descend

The only difference from inorder is where the append sits: record node.val before the two recursive calls. That single line move changes the output order completely — a good reminder that all three DFS traversals are the same walk, differing only in when they look at the node.

2

Why preorder matters

Because the root comes first, preorder is the natural order for copying or serializing a tree — you can rebuild the tree by reading the list left to right. It's also plain DFS order, the same sequence a stack-based explorer would discover nodes in.

3

Iterative version is the easiest of the three

Push root; loop: pop, visit, push right then left (right first so left pops first). No revisiting logic needed since the node is handled the moment it's popped.

04

Solution & live demo

▶1class Solution:
▶2    def preorderTraversal(self, root):
▶3        res = []
▶4        def dfs(node):
▶5            if not node:
▶6                return
▶7            res.append(node.val)
▶8            dfs(node.left)
▶9            dfs(node.right)
▶10        dfs(root)
▶11        return res

05

Common pitfalls

Pushing children onto a stack left-first

✗ Wrong

stack.append(node.left)
stack.append(node.right)

✓ Right

if node.right: stack.append(node.right)
if node.left: stack.append(node.left)

In the iterative version a stack reverses insertion order, so pushing left first pops it second and the traversal mirrors. The right child must go on first for the left to be visited first.

Confusing it with level order

✗ Wrong

# BFS with a queue

✓ Right

res.append(node.val)
dfs(node.left)
dfs(node.right)

Preorder descends fully into the left subtree before touching the right; level order sweeps rank by rank. They agree on the root and diverge immediately after, which makes the mistake easy to miss on tiny test trees.

Appending inside the null check

✗ Wrong

if not node:
    res.append(None)
    return

✓ Right

if not node:
    return

Null placeholders belong in serialisation, not in a traversal that reports values. Emitting them corrupts the output length and any index-based reconstruction downstream.

06

Edge cases

Empty tree

Base case returns immediately — empty list.

Only right children

Each node is visited then recursion slides right; output equals the top-to-bottom chain.

Single node

Visited immediately; both child calls hit the base case.

07

Complexity

Time

O(n)

Space

O(h)

One visit per node; stack depth bounded by tree height.