Binary Tree Preorder Traversal

Problem Summary

• Given a binary tree, return its Pre-order Traversal in a list

Approach Taken

• You can run Pre-order Traversal recursively or iteratively

Main Concepts Used

• Trees
• Pre-order Traversal

Time & Space Complexity

• Time: $O(n)$ → Reason: Going through each node
• Space: $O(n)$ → Reason: Storing each node

Recursive Code

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def traverse(root):
            if not root:
                return

            output.append(root.val)
            traverse(root.left)
            traverse(root.right)

        output = []
        traverse(root)
        return output

Iterative Code

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []

        order = [root]
        output = []

        while order:
            current = order.pop()
            output.append(current.val)
            if current.right:
                order.append(current.right)
            if current.left:
                order.append(current.left)
        return output

Common mistakes

• Using Queue instead of a Stack
• Adding left child first in the iterative approach