Morris Preorder Traversal

Hard TUF ID 138 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Return the preorder traversal of a binary tree (node, then left subtree, then right subtree) as a list of values, using only O(1) extra memory besides the output: no recursion and no explicit stack. The tree may be modified during the traversal, but it must be restored exactly before the method returns.

Constraints (LeetCode 144): up to 100 nodes, values in [-100, 100]. The memory bound is the point of the exercise; the Java file also runs a 100000-node tree and checks that the tree is unchanged afterwards.

Example 1

        1
       / \
      2   3
     / \   \
    4   5   6
answer = [1, 2, 4, 5, 3, 6]

Each node appears before everything below it, and a left subtree is listed completely before the matching right subtree.

Example 2

root = [1, null, 2, 3]      // 1 has a right child 2, and 2 has a left child 3
answer = [1, 2, 3]

Approach 1: Recursion

Intuition. Follow the definition: record the node, traverse its left subtree, traverse its right subtree. It is short and obviously correct, and it gives us the expected output for testing the other methods. Its memory cost is the call stack, O(h).

Algorithm.

If the node is null, return.
Append the node’s value, recurse left, recurse right.

static List<Integer> recursive(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    preorder(root, out);
    return out;
}

static void preorder(TreeNode node, List<Integer> out) {
    if (node == null) return;
    out.add(node.val);
    preorder(node.left, out);
    preorder(node.right, out);
}

Complexity. Time O(n), each node visited once. Space O(h) for the call stack: O(log n) balanced, O(n) for a chain.

Approach 2: Explicit stack

Intuition. Pop a node, record it, then push its right child and then its left child. The stack is last-in-first-out, so the left child is handled next, and the right child stays buried until the whole left subtree has been popped. This removes recursion but the stack can still hold up to about h nodes.

Algorithm.

If the root is null, return an empty list; otherwise push it.
While the stack is not empty: pop, record, push right child, push left child (skipping nulls).

static List<Integer> iterative(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    if (root == null) return out;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        out.add(node.val);
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
    return out;
}

Complexity. Time O(n), each node pushed and popped once. Space O(h).

Approach 3: Morris traversal

Intuition. In both approaches above, the extra memory exists only to remember where to continue after a left subtree is finished. For a node cur, the traversal of its left subtree always ends at the rightmost node of that subtree, which we will call pred (it is cur’s inorder predecessor). That node’s right pointer is null, so it is free to use.

Morris traversal plants a temporary link pred.right = cur, a thread, before going left. When the left subtree is finished, the walk reaches pred, follows right as it would for any node, and lands back on cur. The way back up is stored in the tree, not in a stack.

Every node with a left child is therefore reached twice. To tell which arrival we are on, we search for pred again: if pred.right is null, it is the first arrival; if pred.right == cur, we have come back through the thread.

The only difference from Morris inorder is when a node is recorded. Preorder wants a node before its left subtree, so we record it on the first arrival, at the moment the thread is planted. On the second arrival the node has already been recorded; we just remove the thread and move right. Nodes with no left child are recorded immediately in both variants.

Algorithm.

cur = root.
While cur != null:
- If cur.left == null: record cur, set cur = cur.right.
- Otherwise find pred, the rightmost node of cur.left, stopping if pred.right == cur.
  - If pred.right == null (first arrival): record cur, set pred.right = cur, then cur = cur.left.
  - Otherwise (second arrival): set pred.right = null, then cur = cur.right.

static List<Integer> morris(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left == null) {                  // no left subtree: visit and move right
            out.add(cur.val);
            cur = cur.right;                     // real child or a thread back up
            continue;
        }
        TreeNode pred = cur.left;                // rightmost node of the left subtree
        while (pred.right != null && pred.right != cur) pred = pred.right;
        if (pred.right == null) {                // first arrival: preorder visits the node now
            out.add(cur.val);
            pred.right = cur;                    // thread to find the way back after the left subtree
            cur = cur.left;
        } else {                                 // second arrival: already visited, just clean up
            pred.right = null;
            cur = cur.right;
        }
    }
    return out;
}

Dry run on Example 1:

`cur`	situation	action	output so far
1	pred = 5, no thread	record, thread 5 → 1, go left	1
2	pred = 4, no thread	record, thread 4 → 2, go left	1, 2
4	no left child	record, follow right (thread) to 2	1, 2, 4
2	pred = 4, thread found	remove thread, go right	1, 2, 4
5	no left child	record, follow right (thread) to 1	1, 2, 4, 5
1	pred = 5, thread found	remove thread, go right	1, 2, 4, 5
3	no left child	record, go right	1, 2, 4, 5, 3
6	no left child	record, go right (`null`)	1, 2, 4, 5, 3, 6

Both threads are removed on the second arrivals, so the tree is restored.

Complexity. Time O(n). Each predecessor search walks the right spine of cur.left. A given edge x → x.right lies on that spine for at most one node cur, and each spine is walked twice (to plant and to remove the thread), so all searches together cost O(n). Space O(1) besides the output list.

Edge cases and pitfalls

Empty tree. The loop does not run; the result is empty.
Record before planting. Recording on the second arrival instead of the first produces inorder, not preorder. The two Morris variants differ only in this line, so it is a common slip.
Predecessor loop condition. Stop on pred.right == null or pred.right == cur. Without the second test, the search on the second arrival follows the thread into cur and never terminates.
Breaking out early. If you stop the loop before it ends (for example, after finding a target value), some threads remain and the tree may contain cycles. Finish the traversal or undo the threads. The tests compare the tree with a deep copy after each run and then run Morris again on the same tree.
Thread detection by reference. pred.right == cur compares node identity, so equal values elsewhere in the tree cannot confuse it. The tests include a tree whose values are all 2 except one.
Not thread-safe. The tree is rewired temporarily, so it must not be read concurrently.

Morris Inorder Traversal is the same algorithm, recording on the second arrival.
Preorder Traversal covers the recursive and stack versions in more detail.
Morris Preorder Traversal of a Binary Tree is the same problem in the A2Z sheet.
Flatten Binary Tree to Linked List rewires the rightmost node of the left subtree permanently, in preorder.
Serialize and De-serialize BT is usually written with a preorder walk.

Morris Preorder Traversal

Problem

Approach 1: Recursion

Approach 2: Explicit stack

Approach 3: Morris traversal

Edge cases and pitfalls

Related problems