Binary Tree Preorder Traversal

Easy · Graphs · Explanation and code example

Morris Traversal

How it works

Morris Traversal lets us do preorder traversal without recursion and without a stack, using O(1) extra space.

The key idea:

For every node with a left child, find its inorder predecessor (rightmost node in the left subtree).
Normally, after finishing the left subtree, we would return back to the root.
Since we have no stack, we temporarily create a thread:
predecessor.right = current
On the first time we reach a node, we record its value (because preorder = Node → Left → Right).
When we come back through the created thread, we restore the tree by removing the thread and then continue to the right child.

This modifies the tree temporarily but restores it fully at the end.

Steps

Initialize cur = root and an empty result list res.
While cur is not null:
- If cur.left does NOT exist:
  - Visit cur (append value to res).
  - Move to cur.right.
- Else:
  - Find the inorder predecessor prev (rightmost node in cur.left).
  - If prev.right is null:
    - This is the first time visiting cur.
    - Append cur.val to res.
    - Create a thread: prev.right = cur.
    - Move to cur.left.
  - Else:
    - Thread exists → we are returning after finishing the left subtree.
    - Remove the thread: prev.right = None.
    - Move to cur.right.
Return res.

Complexity

Time complexity: O(n)
Space complexity:
- O(1) extra space.
- O(n) space for the output array.

Things to watch for

Adding Node Value After Recursing on Children

Preorder requires visiting the current node before its children. Adding the value after recursive calls produces postorder traversal instead.

Pushing Left Child Before Right in Stack-Based Approach

In the iterative approach, the right child must be pushed onto the stack before the left child. Since stacks are LIFO, pushing left first causes right to be processed first.

Python code example

from typing import List, Optional

# 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 = []
        cur = root

        while cur:
            if not cur.left:
                res.append(cur.val)
                cur = cur.right
            else:
                prev = cur.left
                while prev.right and prev.right != cur:
                    prev = prev.right

                if not prev.right:
                    res.append(cur.val)
                    prev.right = cur
                    cur = cur.left
                else:
                    prev.right = None
                    cur = cur.right

        return res

C++ code example

/**
 * 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> res;
        TreeNode* cur = root;

        while (cur) {
            if (!cur->left) {
                res.push_back(cur->val);
                cur = cur->right;
            } else {
                TreeNode* prev = cur->left;
                while (prev->right && prev->right != cur) {
                    prev = prev->right;
                }

                if (!prev->right) {
                    res.push_back(cur->val);
                    prev->right = cur;
                    cur = cur->left;
                } else {
                    prev->right = nullptr;
                    cur = cur->right;
                }
            }
        }

        return res;
    }
};

Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations