How hard is LeetCode 144. Binary Tree Preorder Traversal?

LeetCode 144. Binary Tree Preorder Traversal is rated Easy on LeetCode.

What is the time complexity of LeetCode 144. Binary Tree Preorder Traversal?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 144. Binary Tree Preorder Traversal?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 144. Binary Tree Preorder Traversal cover?

LeetCode 144. Binary Tree Preorder Traversal is tagged Stack, Tree, Depth-First Search and Binary Tree on LeetCode.

Binary Tree Preorder Traversal — LeetCode 144 Python Solution

EasyStackTreeDepth-First SearchBinary Tree

Problem: #144
Pattern: Stack
Reading time: 3 min
Source: leetcode.com

The problem

Given the root of a binary tree, return the preorder traversal of its nodes' values.

Python solution

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def dfs(root):
            if root is None:
                return
            ans.append(root.val)
            dfs(root.left)
            dfs(root.right)

        ans = []
        dfs(root)
        return ans

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 144. Binary Tree Preorder Traversal is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Stack.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 144. Binary Tree Preorder Traversal?: LeetCode 144. Binary Tree Preorder Traversal is rated Easy on LeetCode.
What is the time complexity of LeetCode 144. Binary Tree Preorder Traversal?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 144. Binary Tree Preorder Traversal?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 144. Binary Tree Preorder Traversal cover?: LeetCode 144. Binary Tree Preorder Traversal is tagged Stack, Tree, Depth-First Search and Binary Tree on LeetCode.