# Binary Tree Preorder Traversal
**Difficulty:** EASY
[External](https://leetcode.com/problems/binary-tree-preorder-traversal)
Canonical: https://scaleengineer.com/dsa/problems/binary-tree-preorder-traversal
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Stack, Tree, Binary Tree
**Companies:** [Yahoo](https://scaleengineer.com/companies/yahoo)
---
## Problem
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\]

**Explanation:**

![](https://assets.glich.co/dsa/binary-tree-preorder-traversal/image0.png)

**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\]

**Explanation:**

![](https://assets.glich.co/dsa/binary-tree-preorder-traversal/image1.png)

**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`

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

# Approaches
## Recursive Approach
The most intuitive way to perform a preorder traversal is using recursion. The preorder traversal follows the order: **Root -> Left -> Right**. A recursive function can naturally implement this by processing the current node, then making a recursive call for the left child, followed by a recursive call for the right child.
**Time:** O(N), as each node is visited exactly once. · **Space:** O(H), where H is the height of the tree. In the worst case of a skewed tree, this is O(N).
**Pros:** Simple and intuitive to understand and implement.; The code directly reflects the definition of preorder traversal.
**Cons:** Can lead to a `StackOverflowError` for very deep or skewed trees due to the depth of recursion.; The space complexity is dependent on the height of the tree, which can be O(N) in the worst case.
### Explanation
This approach uses a helper function that takes the current node and a list to store the results. The base case for the recursion is when the node is `null`. Otherwise, it first adds the current node's value to the list, then makes a recursive call on the left child, and finally on the right child. This order of operations perfectly matches the definition of preorder traversal.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        traverse(root, result);
        return result;
    }

    private void traverse(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }
        result.add(node.val);       // Visit the root
        traverse(node.left, result);  // Traverse left subtree
        traverse(node.right, result); // Traverse right subtree
    }
}
```
### Algorithm
- Create a helper function, say `traverse(node, resultList)`.
- If the current `node` is `null`, return.
- Add the `node.val` to the `resultList` (visiting the root).
- Recursively call `traverse(node.left, resultList)` to traverse the left subtree.
- Recursively call `traverse(node.right, resultList)` to traverse the right subtree.

## Iterative Approach using a Stack
To avoid the limitations of recursion, we can implement the preorder traversal iteratively using an explicit stack. This approach mimics the behavior of the recursion call stack. We process a node, then push its children onto the stack to be processed later. Since a stack is a Last-In-First-Out (LIFO) data structure, we push the right child first, then the left child, to ensure the left subtree is processed before the right subtree.
**Time:** O(N), as each node is pushed and popped from the stack exactly once. · **Space:** O(H), where H is the height of the tree. In the worst case of a skewed tree, this is O(N).
**Pros:** Avoids recursion depth limits and the potential for stack overflow.; Can handle very deep trees that would fail with a recursive approach.
**Cons:** Requires extra space for the stack, which can be up to O(N) for a skewed tree.
### Explanation
This method replaces the implicit function call stack of recursion with an explicit `Stack` data structure. We start by pushing the root node. In each iteration of the loop, we pop a node, add its value to our result list, and then push its children onto the stack. Crucially, the right child is pushed before the left child. This ensures that the left child, being on top of the stack, is popped and processed next, correctly following the preorder (Root, Left, Right) sequence.

```java
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);

            // Push right child first so that left child is processed first
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return result;
    }
}
```
### Algorithm
- Initialize an empty list `result`.
- If the `root` is `null`, return the empty list.
- Create an empty `Stack` and push the `root` node onto it.
- While the stack is not empty:
  - Pop a node from the stack.
  - Add the node's value to the `result` list.
  - Push the right child onto the stack if it exists.
  - Push the left child onto the stack if it exists. (Note: Push right child first so left is processed first).
- Return the `result` list.

## Morris Traversal
Morris Traversal is an advanced, highly space-efficient technique that performs a traversal in O(1) auxiliary space. It achieves this by temporarily modifying the tree's structure. It creates temporary links (threads) from the inorder predecessor of a node back to the node itself, allowing traversal back up the tree without a stack or recursion. After the subtree is visited, these links are removed to restore the original tree structure.
**Time:** O(N). Although there's a nested loop, each edge is traversed at most twice, leading to an amortized linear time complexity. · **Space:** O(1), as no extra space proportional to the input size is used besides the output list.
**Pros:** Extremely space-efficient with O(1) auxiliary space (excluding the output list).; Does not use recursion or an explicit stack, making it very robust.
**Cons:** The algorithm is complex and harder to understand and implement correctly.; It temporarily modifies the input tree, which might not be permissible in all scenarios (though it does restore the tree's original structure).
### Explanation
The core idea is to traverse the tree without recursion or a stack. When at a `current` node, we check if it has a left child. If not, we visit it and move right. If it does, we find its inorder predecessor. We then use the predecessor's `right` pointer (which is normally `null`) to create a temporary link back to the `current` node. For preorder, we visit the `current` node's value *before* traversing the left subtree (i.e., when we create the link). After the left subtree is fully traversed, we revisit the `current` node via this link, at which point we remove the link and move to the right subtree.

```java
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        TreeNode current = root;
        while (current != null) {
            if (current.left == null) {
                result.add(current.val);
                current = current.right;
            } else {
                // Find the inorder predecessor of current
                TreeNode predecessor = current.left;
                while (predecessor.right != null && predecessor.right != current) {
                    predecessor = predecessor.right;
                }

                if (predecessor.right == null) {
                    // This is the first time we visit this node.
                    // Visit the node, create the thread, and move to the left.
                    result.add(current.val);
                    predecessor.right = current;
                    current = current.left;
                } else {
                    // The thread already exists. We have visited the left subtree.
                    // Remove the thread and move to the right.
                    predecessor.right = null;
                    current = current.right;
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- Initialize an empty list `result` and set `current` pointer to `root`.
- While `current` is not `null`:
  - If `current` has no left child, add its value to `result` and move `current` to its right child.
  - If `current` has a left child, find its inorder predecessor (the rightmost node in the left subtree).
    - If the predecessor's right child is `null`: Add `current.val` to `result`, create a temporary link from the predecessor's right child to `current`, and move `current` to its left child.
    - If the predecessor's right child is `current`: Break the temporary link and move `current` to its right child.
- Return `result`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List < Integer > preorderTraversal ( TreeNode root ) { List < Integer > ans = new ArrayList <>(); while ( root != null ) { if ( root . left == null ) { ans . add ( root . val ); root = root . right ; } else { TreeNode prev = root . left ; while ( prev . right != null && prev . right != root ) { prev = prev . right ; } if ( prev . right == null ) { ans . add ( root . val ); prev . right = root ; root = root . left ; } else { prev . right = null ; root = root . right ; } } } return ans ; } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector < int > preorderTraversal ( TreeNode * root ) { vector < int > ans ; while ( root ) { if ( ! root -> left ) { ans . push_back ( root -> val ); root = root -> right ; } else { TreeNode * prev = root -> left ; while ( prev -> right && prev -> right != root ) { prev = prev -> right ; } if ( ! prev -> right ) { ans . push_back ( root -> val ); prev -> right = root ; root = root -> left ; } else { prev -> right = nullptr ; root = root -> right ; } } } return ans ; } };
```

### 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 : Optional [ TreeNode ]) -> List [ int ]: ans = [] while root : if root . left is None : ans . append ( root . val ) root = root . right else : prev = root . left while prev . right and prev . right != root : prev = prev . right if prev . right is None : ans . append ( root . val ) prev . right = root root = root . left else : prev . right = None root = root . right return ans
```