Leetcode 144. Binary Tree Preorder Traversal

Problem

Leetcode 144 - Binary Tree Preorder Traversal

Example:

Input: root = [1,null,2,3]

Output: [1,2,3]

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]

Output: [1,2,4,5,6,7,3,8,9]

Input: root = []
Output: []

Input: root = [1]
Output: [1]

Approach

When we run the DFS, we can first append the root’s value into the list that we’re planning to return then go left, and right

Here is the Python code for the solution:

class Solution:
    # recurisve solution
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []

        def inorder(root):
            if not root:
                return
            
            res.append(root.val)
            inorder(root.left)
            inorder(root.right)
        
        return res
        
    # iterative solution
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        stack = []
        res = []
        curr = root

        while curr or stack:
            if curr:
                res.append(curr.val)
                stack.append(curr.right)
                curr = curr.left
            else:
                curr = stack.pop()
        
        return res

Time Complexity and Space Complexity

Recursion Method:

Time Complexity: $O(n)$

Space Complexity: $O(n)$

Iterative Method:

Time Complexity: $O(n)$

Space Complexity: $O(n)$