☕ DSA Java Articles

Topics › Binary Trees › Hard Problems

Morris Preorder Traversal of a Binary Tree

Hard TUF ID 2791 A2Z

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 space apart from the output list. No recursion and no explicit stack. You may modify the tree temporarily, but it must be exactly as it was when the method returns.

Constraints (LeetCode 144): up to 100 nodes, values in [-100, 100]. The space restriction is the point of the exercise; the Java file tests a 100000-node tree as well.

Example 1

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

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. Preorder is defined recursively, so the code is the definition: record the node, traverse the left subtree, traverse the right subtree. The call stack remembers where to continue after the left subtree is finished.

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 is visited once. Space O(h) for the call stack, where h is the height; that is O(n) for a skewed tree.

Approach 2: Explicit stack

Intuition. Replace the call stack with our own. Pop a node, record it, then push its right child before its left child, so that the left child is popped (and its whole subtree finished) first.

static List<Integer> iterativeStack(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    if (root == null) return out;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode cur = stack.pop();
        out.add(cur.val);
        if (cur.right != null) stack.push(cur.right);       // pushed first so the left child is popped first
        if (cur.left != null) stack.push(cur.left);
    }
    return out;
}

Complexity. Time O(n). Space O(h) for the stack in the worst case. The memory has moved from the call stack to the heap, but it has not gone away.

Approach 3: Morris traversal

Intuition. What is the stack actually for? When we go down into the left subtree of a node cur, we need a way to come back to cur afterwards so that we can continue with cur.right. Morris’s observation is that the tree already has a convenient place to store that “way back”:

Morris temporarily sets pred.right = cur. This pointer is called a thread. After the left subtree has been walked, following right pointers from pred leads straight back to cur. When we arrive at cur the second time, we find the thread (pred.right == cur), remove it, and move on to cur.right. So each node with a left child is reached twice, and the thread tells us which time it is:

A node without a left child is recorded immediately and we move right. That right pointer is either a real child or a thread leading back up.

Algorithm.

  1. cur = root. While cur != null:
  2. If cur.left == null: record cur, set cur = cur.right.
  3. Otherwise find pred: start at cur.left and move right while pred.right is neither null nor cur.
    • If pred.right == null: record cur, set pred.right = cur, then cur = cur.left.
    • Else (pred.right == cur): 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) {
            out.add(cur.val);
            cur = cur.right;
        } else {
            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: visit, leave a thread back, go left
                out.add(cur.val);
                pred.right = cur;
                cur = cur.left;
            } else {                                         // second arrival via the thread: left side is done
                pred.right = null;
                cur = cur.right;
            }
        }
    }
    return out;
}

Dry run on Example 1:

cur left child? pred pred.right was action output so far
1 yes 5 null record 1, thread 5→1, go left 1
2 yes 4 null record 2, thread 4→2, go left 1 2
4 no     record 4, follow 4.right (thread) to 2 1 2 4
2 yes 4 2 remove thread, go right 1 2 4
5 no     record 5, follow 5.right (thread) to 1 1 2 4 5
1 yes 5 1 remove thread, go right 1 2 4 5
3 no     record 3, go right 1 2 4 5 3
6 no     record 6, go right (null) 1 2 4 5 3 6

Both threads were removed, so the tree is back to its original shape.

Complexity. Time O(n). The predecessor search looks expensive, but each search walks down the right spine of one left subtree, and every such spine is walked exactly twice in total: once when the thread is created and once when it is removed. Spines of different nodes do not share edges, so all searches together cost O(n). Space O(1) beyond the output: a couple of pointers.

Morris preorder versus Morris inorder

The two algorithms are identical except for where the node is recorded. Preorder records it on the first arrival, before going left. Inorder records it on the second arrival, after the left subtree is done. If you can write one, change one line and you have the other.

Edge cases and pitfalls