[link](https://leetcode.com/problems/binary-tree-preorder-traversal/)

---

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

#### Example 3:

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

#### Constraints:

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

Follow up: Recursive solution is trivial, could you do it iteratively?

---

The preorderTraversal function performs a pre-order traversal on a binary tree and returns a list of node values visited in pre-order. In pre-order traversal, the nodes are visited in the order: root, left subtree, right subtree. To achieve this, the function uses a recursive approach. The function first initializes an empty list called res, which will store the result of the traversal.

Then, it defines a nested function called dfs (short for depth-first search), which is responsible for the recursive traversal. The dfs function takes a node as input, representing the current node being processed.

If the current node is None (i.e., it's a leaf or empty node), the function returns without doing anything, as there is no node to process. If the node is not None, it appends the value of the node to the res list. This step corresponds to visiting the root of the current subtree. The function then recursively calls dfs on the left child of the current node (dfs(node.left)), which corresponds to traversing the left subtree. After the left subtree traversal is complete, the function then recursively calls dfs on the right child of the current node (dfs(node.right)), which corresponds to traversing the right subtree. The function starts the recursive traversal from the root of the binary tree by calling dfs(root). This effectively traverses the entire tree in pre-order and stores the node values in the res list.

#### Solution 1: Recursive solution

# 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(node):
            if not node:
                return 
            res.append(node.val)
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return res

O(T): O(n)
O(S): O(h)

---

The preorderTraversal function performs a pre-order traversal on a binary tree and returns a list of node values visited in pre-order. Instead of using a recursive approach as in the previous implementation, this function uses an iterative approach with a stack to simulate the recursion. The function initializes an empty list called stack, which will be used to store nodes during the traversal. It also initializes an empty list called res, which will store the result of the traversal. The variable cur is set to the root of the binary tree. The traversal starts by checking whether the stack is not empty (stack or cur). The loop continues until both the stack is empty, and there is no current node (cur) to process.

In each iteration of the loop:

If cur is not None, it means there is a node to process. In this case, the value of the current node (cur.val) is appended to the res list, which corresponds to visiting the root of the current subtree.

If the right child of the current node (cur.right) exists, it is pushed onto the stack to be processed later. This step ensures that the right subtree will be visited after the left subtree.
The current node (cur) is then updated to its left child (cur = cur.left). This step corresponds to traversing the left subtree. The process continues until cur becomes None, at which point the loop moves to the else block.

If cur is None, it means that the left subtree of the current node has been completely traversed. In this case, a node is popped from the stack (if there is any) and assigned to cur. This node will be processed next, and its right subtree will be traversed. The loop then repeats, and the process continues with the new cur node.

#### Solution 2: Iterative solution

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        stack = []
        res = []
        cur = root
        while stack or cur:
            if cur:
                res.append(cur.val)
                if cur.right:
                    stack.append(cur.right)
                cur = cur.left
            else:
                cur = stack.pop()
        return res
                

O(T): O(n)
O(S): O(h)