The challenge
Produce inorder traversal without recursion or an auxiliary stack.
The tree must be mutable and exclusively accessible during traversal. Complete the traversal so every temporary pointer is removed.
Example
The balanced example outputs [2, 4, 6, 8, 10, 12, 14] and ends with the original tree.
Use the walkthrough below to inspect the input and each state change.
See Morris, step by step
Follow the branches. Watch the state change.
View child pointers & node state
| Node | Value | Left | Right | State |
|---|---|---|---|---|
| A | 8 | B | C | — |
| B | 4 | D | E | — |
| C | 12 | F | G | — |
| D | 2 | null | null | — |
| E | 6 | null | null | — |
| F | 10 | null | null | — |
| G | 14 | null | null | — |
Inspect the input.
Labels identify node objects; numbers are their values. Left and right child pointers define the tree.
root = A:8View original input
A:8 [L:B, R:C] · B:4 [L:D, R:E] · C:12 [L:F, R:G] · D:2 [L:null, R:null] · E:6 [L:null, R:null] · F:10 [L:null, R:null] · G:14 [L:null, R:null]
Node IDs stay distinct even when values repeat. Pointer mutations update the diagram; removed nodes remain in the state table for reference.
Put it into code
Use an unused predecessor right pointer as a temporary return address.
Nodes store value, left, and right. C++ uses C++17 or later.
from collections import deque
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def morris_inorder(root):
out, node = [], root
while node:
if not node.left:
out.append(node.value)
node = node.right
else:
pred = node.left
while pred.right and pred.right is not node:
pred = pred.right
if pred.right is None:
pred.right = node
node = node.left
else:
pred.right = None
out.append(node.value)
node = node.right
return out
#include <algorithm>
#include <cmath>
#include <functional>
#include <limits>
#include <map>
#include <optional>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
struct Node {
long long value;
Node *left = nullptr, *right = nullptr;
explicit Node(long long v) : value(v) {}
};
vector<long long> morris_inorder(Node* root) {
vector<long long> out;
Node* node = root;
while (node) {
if (!node->left) {
out.push_back(node->value); node = node->right;
} else {
Node* pred = node->left;
while (pred->right && pred->right != node) pred = pred->right;
if (!pred->right) { pred->right = node; node = node->left; }
else {
pred->right = nullptr;
out.push_back(node->value); node = node->right;
}
}
}
return out;
}