# 144. Binary Tree Preorder Traversal

### Solution 1: Non-recursive

{% tabs %}
{% tab title="While loop" %}

> This is "while loop" method using stack

1. Use a list as stack, stack.pop() moves top element, stack.append() pushes element to top. Because Python doesn't have stack data structure
2. Append root to result list directly, push right leaf to stack, then push left leaf to stack
3. Poop out an element, which is a new root so append it to result list, then push its right leaf to stack, then push left leaf to stack
4. Until stack is empty

{% hint style="danger" %}
add root.val to result list instead of root, but operate root/left/right in stack list
{% endhint %}

{% endtab %}

{% tab title="Python" %}

```python
# 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: TreeNode) -> List[int]:
        # consider edge case
        result = []
        stack = []
        if root == None:
            return result
        
        # regular case
        stack.append(root)
        while len(stack) > 0:
            root = stack.pop()
            result.append(root.val)
            if root.right != None:
                stack.append(root.right)
            if root.left != None:
                stack.append(root.left)
        return result
```

{% endtab %}

{% tab title="Java" %}

```java
// Some code
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer> ();
        Stack<TreeNode> stack = new Stack<TreeNode> ();
        
        // edge case
        if(root == null)
            return res;
            
        // regular case
        stack.push(root);
        while(stack.size() > 0) {
            root = stack.pop();
            res.add(root.val);
            if(root.right != null)
                stack.push(root.right);
            if(root.left != null)
                stack.push(root.left);
        }
        
        return res;
    }
}
```

{% endtab %}
{% endtabs %}

### Solution 2: Recursive

{% tabs %}
{% tab title="Recursive" %}

> Using help function to do recurcive, result list as one of two parameters, when root=None, return
>
> Add root, traversal left, then right
>
> return `result` at the end of whole functions

1. Self define a traversal function, pass "root" and "result", so that "result" can be changed following recursive
2. Add root.val to result, and traversal left, then right
3. When root=None, return from sub-function
4. return result in main function

{% hint style="danger" %}
In sub-function, only return and pass result list as a parameter; In main function, return result list???

If return result list in sub-function, it is useless because result has been passed as a parameter. In main function, if return sub-function, then the result list will be None.Because it only returns initial result lis. Why? I tried, but don't know why.
{% endhint %}
{% endtab %}

{% tab title="Python" %}

```python
# 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: TreeNode) -> List[int]:
        res = []
        self.traversal(root, res)
        return res
    
    def traversal(self, root, res):
        # stop condition
        if root == None:
            return
        
        # regular case
        res.append(root.val)
        self.traversal(root.left, res)
        self.traversal(root.right, res)
```

{% endtab %}

{% tab title="Java" %}

```java
// Some code
class Solution {
    final List<Integer> res = new ArrayList<> ();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root == null) return res;
        
        res.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return res;
    } 
}
```

{% endtab %}
{% endtabs %}

### Solution 3: Divide & Conquer

{% tabs %}
{% tab title="Divide & Conquer" %}

> Recursive the function itself, return result during recursive
>
> Traversal left, right, and combine root, left, right at the end
>
> return `result` immediately in each recursion

1. Initialize result list
2. Return result list if satisfied stop condition
3. Divide binary tree to root, left and right
4. Conquer to do recursive
5. Combine them again to get the completed result

{% hint style="danger" %}
When combine, using `result.extend()` instead of `result.append()`. Because `extend` means only add the elements of that list to another list, but `append` adds whole list directly
{% endhint %}
{% endtab %}

{% tab title="Python" %}

```python
# 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: TreeNode) -> List[int]:def preorderTraversal(self, root: TreeNode) -> List[int]:
        # consider edge case
        result = []
        if root == None:
            return result
        
        # regular case
        # divide
        left = self.preorderTraversal(root.left)
        right = self.preorderTraversal(root.right)
        
        # conquer
        result.append(root.val)
        result.extend(left)
        result.extend(right)
        return result
```

{% endtab %}
{% endtabs %}