---
link: https://leetcode.com/problems/binary-tree-preorder-traversal/
tags: tree, bt
---

# 144. Binary Tree Preorder Traversal

## Question
Given a binary tree, return the *preorder* traversal of its nodes' values.

**Example:**

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,2,3]

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

## Solution: 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 preorderTraversalRecursive(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        result = []
        self.helper(root, result)
        return result
    
    def helper(self, node, result):
        if node is None:
            return
        
        result.append(node.val)
        
        self.helper(node.left, result)
        self.helper(node.right, result)
    
    
    def preorderTraversal(self, root):
        from collections import deque
        stack = deque()
        stack.append((False, root))  # IsAppendingResult, Node
        result = []
        
        while stack:
            is_appending_result, node = stack.pop()
            
            if node is None:
                continue
                
            if is_appending_result:
                result.append(node.val)
            else:
                stack.extend([(False, node.right), (False, node.left), (True, node)])
        return result

## Solution: Java