EasyStackTreeDepth-First SearchBinary Tree

Binary Tree Preorder Traversal

1 approach, code in every language

You are given the root of a binary tree. Return the values of its nodes visited in preorder sequence.

A preorder traversal records the current node first, then traverses the entire left subtree, and finally the entire right subtree. Because the node comes before its descendants, the root always appears first and each subtree's root leads its own block of values.

This root-first ordering is commonly used to serialize a tree or to clone its structure top-down.

Example 1

Input: root = [1,null,2,3]

Output: [1,2,3]

Visit root 1, then its right child 2 (no left child), then 2's left child 3.

Example 2

Input: root = [1,2,3,4,5]

Output: [1,2,4,5,3]

Record 1, descend left to 2, then its children 4 and 5, then return to the root's right child 3.

Constraints

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

Iterative with Explicit Stack

Use a stack, popping a node to record it, then pushing its right child before its left.

Loading animation…

Intuition

The recursive form is trivial (record node, recurse left, recurse right), but we can convert it into an iterative loop with a single explicit stack. A stack is last-in-first-out, so if we want the left child processed before the right child, we must push the right child first and the left child second. Then each iteration pops a node, records it immediately (satisfying the node-first rule), and schedules its children. This guarantees that whenever we pop, we are always looking at the next node in preorder.

Algorithm walkthrough

1Return an empty list right away if the root is null.
2Initialize a stack containing only the root node.
3While the stack is not empty, pop the top node and append its value to the result.
4Push the node's right child if it exists so it is handled after the left branch.
5Push the node's left child if it exists so it is popped and handled next.
6Continue until the stack empties, then return the collected values.

Implementation

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        result: List[int] = []
        stack: List[TreeNode] = [root]
        while stack:
            node = stack.pop()
            result.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return result

Time

O(n)

Space

O(h)

Each node is pushed and popped exactly once. The stack holds at most O(h) nodes at a time, where h is the tree height; a plain recursive version has the same bounds.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Trees & BST

After the pattern

Now solve one you haven't seen.

Survey Order Of A Ventilation Split is our own problem on the technique behind Binary Tree Preorder Traversal: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free