Problem

Solution

Intuition

This problem requires us to complete a pre-order traversal of a tree. Pre-order traversal follows a DFS approach in which the left sub-trees are recursively traveled first and then the right sub-trees. Because it is given as the problem statement, we know that we must use DFS; otherwise, the intuition would be to read the problem statement to understand what kind of traversal is being sought out and determining we would need to use pre-order traversal which would lead us to DFS.

Approach

Implementing a DFS pre-order traversal is fairly simple. We utilize a standard DFS approach of recursively following root nodes and as we are performing a pre-order traversal, we record the root node before going into the left subtree and then the right subtree.

Complexity

• Time complexity: $O(n)$. We visit every node in the tree once achieving linear time complexity.
• Space complexity: $O(n)$. The stack space utilized for a DFS is linear with the number of nodes in the tree.

Code

# 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]:
        res = []

        def dfs(root):
            if not root:
                return
            res.append(root.val)
            dfs(root.left)
            dfs(root.right)
        
        dfs(root)
        return res