144. Binary Tree Preorder Traversal

Easy LeetCode

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

Example 1

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

Output: [1,2,3]

Example 2

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

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

Example 3

Input: root = []

Output: []

Example 4

Input: root = [1]

Output: [1]

Constraints

• The number of nodes in the tree is in the range [0, 100]
• -100 <= Node.val <= 100

How to solve the problem

Code

• DFS (Recursion)

# 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]:
        # Preorder: Root-Left-Right
        ans = []
        def dfs(node):
        # Determine base case first(stop rucursion)
            if node is None:
                return
            ans.append(node.val) # preorder
            dfs(node.left) # left
            dfs(node.right) # right
        dfs(root)
        return ans

• Iterations with stack

# 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]:
        # Determine base case first(stop rucursion)
        if root is None:
            return []
        stack = [root] # Push root into stack first
        result = [] # Define empty array
        while stack:
            node = stack.pop() # Popout root first
            result.append(node.val) # Put the node which was poped out into result
            # result.append(stack.pop().val)
            if node.right:
                stack.append(node.right) # Push right first, cause satck is FILO
            if node.left:
                stack.append(node.left) # Push left next, cause satck is FILO
        return result

Complexity

• Time complexity: O(n), n == number of nodes
• Space complexity: O(n)