Binary Tree Preorder Traversal

Easy
1860.

Binary Tree Preorder Traversal

Binary Tree Preorder Traversal is an easy coding problem on depth-first search, trees and stack, asked in Amazon, Google and Microsoft interviews.

Given the root of a binary tree, return the values of its nodes in preorder: for every node, first the node itself, then everything in its left subtree, then everything in its right subtree.

Example 1

Input
root = [1,null,2,3]
Output
[1,2,3]
Explanation
1 is visited first; its only child is 2, which is visited before its own left child 3.

Example 2

Input
root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output
[1,2,4,5,6,7,3,8,9]
Explanation
The whole left subtree of 1 (rooted at 2) is listed before anything in the right subtree (rooted at 3).

Example 3

Input
root = []
Output
[]

Constraints

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

Follow-up: The recursive walk is short — can you do it iteratively with an explicit stack?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Binary Tree Preorder Traversal — Problem & Solution

Binary Tree Preorder Traversal solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Binary Tree Preorder Traversal is an easy coding problem on depth-first search, trees and stack, asked in Amazon, Google and Microsoft interviews.

Problem statement

Given the root of a binary tree, return the values of its nodes in preorder: for every node, first the node itself, then everything in its left subtree, then everything in its right subtree.

Example 1

Input: root = [1,null,2,3]
Output: [1,2,3]
Explanation: 1 is visited first; its only child is 2, which is visited before its own left child 3.

Example 2

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [1,2,4,5,6,7,3,8,9]
Explanation: The whole left subtree of 1 (rooted at 2) is listed before anything in the right subtree (rooted at 3).

Example 3

Input: root = []
Output: []

Constraints

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

Follow-up: The recursive walk is short — can you do it iteratively with an explicit stack?

Hints for Binary Tree Preorder Traversal

  1. Hint 1

    Preorder records a node the moment you reach it, before either child.

  2. Hint 2

    Recursively: record the node, recurse left, recurse right. The empty subtree records nothing.

  3. Hint 3

    Iteratively, a stack serves nodes last-in-first-out — so push the right child before the left one, and the left subtree is finished first.

How to solve Binary Tree Preorder Traversal

Preorder is node, left subtree, right subtree. A stack reproduces the recursion: pop a node, record it, and push its children so that the left one comes off first.

Approach

  1. If the tree is empty return an empty list; otherwise push the root.
  2. While the stack is not empty, pop a node and append its value.
  3. Push its right child (if any), then its left child (if any).
  4. Return the list.

Why it works

The left child is pushed last, so it is popped next, and every node of its subtree is pushed above the waiting right child — the right subtree is reached only after the entire left subtree has been emptied off the stack. Each node is recorded before any of its descendants, which is the preorder rule.

Complexity

  • Time — O(n)
  • Space — O(h) for the recursion; the stack version holds at most O(h) waiting right children plus the current path

Pitfalls

  • Pushing the left child first visits the right subtree first.
  • Push only non-null children, or the loop has to skip nulls.
  • An empty tree returns [].

Reference solution

Python

from typing import List, Optional

def preorderTraversal(root: Optional[TreeNode]) -> List[int]:
    out = []
    stack = [root] if root is not None else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right is not None:
            stack.append(node.right)
        if node.left is not None:
            stack.append(node.left)
    return out

Java

public static int[] preorderTraversal(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    if (root != null) stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        out.add(node.val);
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
    int[] res = new int[out.size()];
    for (int i = 0; i < res.length; i++) res[i] = out.get(i);
    return res;
}

C++

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> out;
    vector<TreeNode*> stack;
    if (root) stack.push_back(root);
    while (!stack.empty()) {
        TreeNode* node = stack.back();
        stack.pop_back();
        out.push_back(node->val);
        if (node->right) stack.push_back(node->right);
        if (node->left) stack.push_back(node->left);
    }
    return out;
}

JavaScript

var preorderTraversal = function(root) {
    var out = [];
    var stack = root === null ? [] : [root];
    while (stack.length > 0) {
        var node = stack.pop();
        out.push(node.val);
        if (node.right !== null) stack.push(node.right);
        if (node.left !== null) stack.push(node.left);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals