> For the complete documentation index, see [llms.txt](https://lei-d.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lei-d.gitbook.io/leetcode/tree/144binary-tree-preorder-traversal.md).

# 144\_Binary Tree Preorder Traversal

## 144. Binary Tree Preorder Traversal

Level: medium

Tag: tree, stack

## Question

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

### Example 1

```
Given binary tree [1,null,2,3],

   1
    \
     2
    /
   3

return [1,2,3]
```

### Solution 1: recursive

```python
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        ret = []
        self.dfs(root, ret)
        return ret


    def dfs(self, root, ret):
        """
        :type root: TreeNode
        :rtype List[int]
        """
        if root:
            ret.append(root.val)
            self.dfs(root.left, ret)
            self.dfs(root.right, ret)
```

### Another version (w/o defining a helper function)

```python
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        # if root is empty, return empty list
        if not root:
            return []

        # ow, return root value, then left valus and right values
        ret = [root.val]
        if root.left:
            ret += self.preorderTraversal(root.left)
        if root.right:
            ret += self.preorderTraversal(root.right)
        return ret
```

### Solution 2: itratively

```python
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        stack = [root]
        ret = []

        while stack:
            node = stack.pop()
            if node:
                ret.append(node.val)
                stack.append(node.right)
                stack.append(node.left)
        return ret
```