Solution 1 - Recursive DFS

Traverse the binary tree in preorder (root → left → right) using recursion. Visit the current node first, then recursively traverse the left subtree, followed by the right subtree. Collect values in a list as nodes are visited.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0144.1 - Binary Tree Preorder Traversal - Solution 1 - Recursive DFS """

#####################################################################################
# Imports
#####################################################################################
from typing import List, Optional

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """Solution Class"""

    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        """Binary Tree Preorder Traversal Function"""
        result = []

        def dfs(node):
            if not node:
                return
            result.append(node.val)
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return result


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # [1, null, 2, 3] -> [1, 2, 3]
    root = TreeNode(1, None, TreeNode(2, TreeNode(3)))
    print(Solution().preorderTraversal(root))

    # [] -> []
    print(Solution().preorderTraversal(None))

    # [1] -> [1]
    print(Solution().preorderTraversal(TreeNode(1)))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Iterative DFS with Stack

Use an explicit stack to simulate the recursive preorder traversal. Push the root onto the stack, then repeatedly pop a node, record its value, and push its right child first followed by its left child (so left is processed next due to LIFO order).

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0144.2 - Binary Tree Preorder Traversal - Solution 2 - Iterative DFS with Stack """

#####################################################################################
# Imports
#####################################################################################
from typing import List, Optional

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """Solution Class"""

    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        """Binary Tree Preorder Traversal Function"""
        if not root:
            return []

        stack = [root]
        result = []

        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


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # [1, null, 2, 3] -> [1, 2, 3]
    root = TreeNode(1, None, TreeNode(2, TreeNode(3)))
    print(Solution().preorderTraversal(root))

    # [] -> []
    print(Solution().preorderTraversal(None))

    # [1] -> [1]
    print(Solution().preorderTraversal(TreeNode(1)))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

0144 - Binary Tree Preorder Traversal

Solution 1 - Recursive DFS

Solution 2 - Iterative DFS with Stack