Morris Traversal, Threaded Trees & Serialization

                            Mastery target: Level B implementation, progressing toward Level C fluency. You should be able to explain why Morris traversal needs no stack, implement a threaded tree, trace a boundary walk by hand, and serialize/deserialize a tree correctly under interview conditions.
                        

1. Introduction & Motivation

Every traversal covered so far — recursive inorder, preorder, postorder, and BFS with a queue — spends auxiliary space to remember "where to come back to." Recursive traversals spend $O(h)$ call-stack space (worst case $O(n)$ for a skewed tree); an explicit stack-based iterative traversal spends the same. BFS spends $O(w)$ queue space, where $w$ is the widest level. None of them is free.

This lesson asks a sharper question: can a tree be traversed in $O(1)$ auxiliary space, with no stack, no queue, and no recursion? The answer is yes, and the trick is elegant — a leaf's null child pointer is wasted space. Morris traversal temporarily repurposes those null pointers as "threads" back to an ancestor, walks the tree using them, and then removes them to restore the original shape. Threaded binary trees take the same idea and make it permanent, trading a boolean flag per node for a tree that never needs a stack to traverse, forwards or backwards.

The lesson then turns to two problems that do not fit the "visit every node once" traversal family at all: boundary traversal, which reconstructs only the outline of a tree (its left spine, its leaves, its right spine), and serialization/deserialization (LeetCode 297), which converts an entire tree to a string and rebuilds it exactly — the foundation of persisting, transmitting, and testing tree-shaped data.

2. Prerequisites

This lesson builds directly on Complete DSA Series Part 9: Trees. It assumes comfort with recursive inorder/preorder/postorder traversal, BFS level order, and basic pointer manipulation on a binary tree node.

Two traversal topics are deliberately not repeated here because they already have complete, correct implementations in Part 9:

Zigzag level order and vertical order traversal — fully implemented in the BFS Traversal section of Part 9.
Reconstructing a tree from preorder+inorder or inorder+postorder — fully implemented in the Tree Construction section of Part 9.

If you have not worked through those sections, do so before continuing — this lesson only covers the traversal and reconstruction techniques that Part 9 does not: Morris traversal, threaded trees, boundary traversal, and full-tree serialization.

3. Morris Inorder Traversal

                            Core insight: For a node curr with a left child, the node that should be visited immediately after curr finishes its left subtree is its inorder predecessor — the rightmost node in that left subtree. If we temporarily set that predecessor's null right pointer to point back at curr, we have planted a "thread" that lets us return to curr without a stack. Descend left, do the left subtree's work, and when a thread is followed back up, we know the left subtree is done — visit curr now, detect the thread, remove it (restoring the tree exactly to its original shape), and move right. Each edge is walked at most twice, so the whole traversal is $O(n)$ time using only a fixed number of pointer variables — $O(1)$ extra space.
                        

Hand Trace

Trace Morris inorder on a 5-node tree

Tree: root 1, left child 2, right child 3; 2's children are 4 (left) and 5 (right). Expected inorder: 4, 2, 5, 1, 3.

Step	curr	Predecessor	Action	Output so far
1	1	5 (rightmost of 2's subtree)	5.right is null → thread 5→1; curr = 2	[]
2	2	4 (4.right is null)	thread 4→2; curr = 4	[]
3	4	—	no left child → visit 4; curr = 4.right = 2 (thread)	[4]
4	2	4 (4.right is 2 = curr)	thread found → remove it (4.right = null); visit 2; curr = 5	[4, 2]
5	5	—	no left child → visit 5; curr = 5.right = 1 (thread)	[4, 2, 5]
6	1	5 (5.right is 1 = curr)	thread found → remove it (5.right = null); visit 1; curr = 3	[4, 2, 5, 1]
7	3	—	no left child → visit 3; curr = null, loop ends	[4, 2, 5, 1, 3]

Every thread created in step 1 or 2 is removed by step 4 or 6 — the tree is bit-for-bit identical to before the traversal started.

# Morris Inorder Traversal - O(n) time, O(1) extra space

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def morris_inorder(root):
    result = []
    curr = root
    while curr:
        if curr.left is None:
            result.append(curr.val)
            curr = curr.right
        else:
            # Find the inorder predecessor: rightmost node in the left subtree
            pred = curr.left
            while pred.right is not None and pred.right is not curr:
                pred = pred.right

            if pred.right is None:
                pred.right = curr        # create the thread
                curr = curr.left
            else:
                pred.right = None        # thread found - remove it, tree restored
                result.append(curr.val)
                curr = curr.right
    return result

# Test
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print("Morris Inorder:", morris_inorder(root))  # Morris Inorder: [4, 2, 5, 1, 3]

// Morris Inorder Traversal - O(n) time, O(1) extra space
#include <iostream>
#include <vector>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

std::vector<int> morrisInorder(TreeNode* root) {
    std::vector<int> result;
    TreeNode* curr = root;
    while (curr) {
        if (!curr->left) {
            result.push_back(curr->val);
            curr = curr->right;
        } else {
            TreeNode* pred = curr->left;
            while (pred->right && pred->right != curr) {
                pred = pred->right;
            }
            if (!pred->right) {
                pred->right = curr;       // create the thread
                curr = curr->left;
            } else {
                pred->right = nullptr;    // thread found - remove it, tree restored
                result.push_back(curr->val);
                curr = curr->right;
            }
        }
    }
    return result;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    std::vector<int> order = morrisInorder(root);
    std::cout << "Morris Inorder: ";
    for (size_t i = 0; i < order.size(); i++) {
        std::cout << order[i] << (i + 1 < order.size() ? ", " : "\n");
    }
    // Morris Inorder: 4, 2, 5, 1, 3
    return 0;
}

// Morris Inorder Traversal - O(n) time, O(1) extra space
import java.util.*;

public class MorrisInorder {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    static List<Integer> morrisInorder(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left == null) {
                result.add(curr.val);
                curr = curr.right;
            } else {
                TreeNode pred = curr.left;
                while (pred.right != null && pred.right != curr) {
                    pred = pred.right;
                }
                if (pred.right == null) {
                    pred.right = curr;        // create the thread
                    curr = curr.left;
                } else {
                    pred.right = null;        // thread found - remove it, tree restored
                    result.add(curr.val);
                    curr = curr.right;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        System.out.println("Morris Inorder: " + morrisInorder(root)); // [4, 2, 5, 1, 3]
    }
}

4. Morris Preorder Traversal

Morris preorder reuses the exact same threading logic as Morris inorder. The only difference is when a node's value is recorded: inorder records a node the second time it is reached (when the thread is found and removed, after the left subtree is done), while preorder must record a node before descending into its left subtree — the first time it is reached, at the moment the thread is created. Moving that one append/push_back line from the "thread found" branch to the "thread created" branch is the entire change.

# Morris Preorder Traversal - O(n) time, O(1) extra space

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def morris_preorder(root):
    result = []
    curr = root
    while curr:
        if curr.left is None:
            result.append(curr.val)
            curr = curr.right
        else:
            pred = curr.left
            while pred.right is not None and pred.right is not curr:
                pred = pred.right

            if pred.right is None:
                result.append(curr.val)  # visit BEFORE descending left (the one-line diff)
                pred.right = curr
                curr = curr.left
            else:
                pred.right = None        # thread found - remove it, no re-visit needed
                curr = curr.right
    return result

# Test
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print("Morris Preorder:", morris_preorder(root))  # Morris Preorder: [1, 2, 4, 5, 3]

// Morris Preorder Traversal - O(n) time, O(1) extra space
#include <iostream>
#include <vector>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

std::vector<int> morrisPreorder(TreeNode* root) {
    std::vector<int> result;
    TreeNode* curr = root;
    while (curr) {
        if (!curr->left) {
            result.push_back(curr->val);
            curr = curr->right;
        } else {
            TreeNode* pred = curr->left;
            while (pred->right && pred->right != curr) {
                pred = pred->right;
            }
            if (!pred->right) {
                result.push_back(curr->val);  // visit BEFORE descending left
                pred->right = curr;
                curr = curr->left;
            } else {
                pred->right = nullptr;        // thread found - remove it, no re-visit
                curr = curr->right;
            }
        }
    }
    return result;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    std::vector<int> order = morrisPreorder(root);
    std::cout << "Morris Preorder: ";
    for (size_t i = 0; i < order.size(); i++) {
        std::cout << order[i] << (i + 1 < order.size() ? ", " : "\n");
    }
    // Morris Preorder: 1, 2, 4, 5, 3
    return 0;
}

// Morris Preorder Traversal - O(n) time, O(1) extra space
import java.util.*;

public class MorrisPreorder {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    static List<Integer> morrisPreorder(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left == null) {
                result.add(curr.val);
                curr = curr.right;
            } else {
                TreeNode pred = curr.left;
                while (pred.right != null && pred.right != curr) {
                    pred = pred.right;
                }
                if (pred.right == null) {
                    result.add(curr.val);     // visit BEFORE descending left
                    pred.right = curr;
                    curr = curr.left;
                } else {
                    pred.right = null;        // thread found - remove it, no re-visit
                    curr = curr.right;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        System.out.println("Morris Preorder: " + morrisPreorder(root)); // [1, 2, 4, 5, 3]
    }
}

5. Threaded Binary Trees

                            Core insight: Morris traversal creates and destroys threads on the fly. A threaded binary tree makes the same idea permanent: every null right pointer is replaced with a thread to the node's inorder successor, and (in a double-threaded tree) every null left pointer is replaced with a thread to the inorder predecessor. A boolean flag per side records whether that pointer is a real child or a thread. A single-threaded tree (threading only the right pointers, as built below) supports forward iteration without a stack; a double-threaded tree threads both sides, supporting traversal in either direction. Unlike Morris traversal, the threads never come out — the tree stays permanently thread-augmented, which is the right trade-off when a tree will be traversed repeatedly and mutating it back and forth on every pass would be wasteful.
                        

Building the threads requires one inorder pass that links each node to the previously-visited node whenever that previous node's right pointer is still empty. This construction pass itself uses $O(h)$ recursion-stack space (a one-time cost); every traversal after construction is $O(1)$ extra space, because it never recurses or pushes onto a stack again.

# Single Right-Threaded Binary Tree

class ThreadedNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.right_thread = False  # True if `right` is a thread to the inorder successor

def create_threads(root):
    """One-time O(n) pass (uses recursion stack) that adds permanent right threads."""
    prev = [None]  # boxed so the nested function can rebind it

    def visit(node):
        if node is None:
            return
        visit(node.left)
        if prev[0] is not None and prev[0].right is None:
            prev[0].right = node
            prev[0].right_thread = True
        prev[0] = node
        visit(node.right)

    visit(root)
    return root

def leftmost(node):
    while node and node.left:
        node = node.left
    return node

def threaded_inorder(root):
    """No stack, no recursion: O(n) time, O(1) extra space."""
    result = []
    if root is None:
        return result
    node = leftmost(root)
    while node:
        result.append(node.val)
        if node.right_thread:
            node = node.right
        else:
            node = leftmost(node.right) if node.right else None
    return result

# Test - tree: 3 with left child 1, 1's right child 2, root's right child 4
root = ThreadedNode(3)
root.left = ThreadedNode(1)
root.left.right = ThreadedNode(2)
root.right = ThreadedNode(4)

create_threads(root)
print("Threaded Inorder:", threaded_inorder(root))  # Threaded Inorder: [1, 2, 3, 4]

// Single Right-Threaded Binary Tree
#include <iostream>
#include <vector>

struct ThreadedNode {
    int val;
    ThreadedNode* left;
    ThreadedNode* right;
    bool rightThread; // true if `right` is a thread to the inorder successor
    ThreadedNode(int x) : val(x), left(nullptr), right(nullptr), rightThread(false) {}
};

void createThreads(ThreadedNode* node, ThreadedNode*& prev) {
    if (!node) return;
    createThreads(node->left, prev);
    if (prev && !prev->right) {
        prev->right = node;
        prev->rightThread = true;
    }
    prev = node;
    createThreads(node->right, prev);
}

ThreadedNode* leftmost(ThreadedNode* node) {
    while (node && node->left) node = node->left;
    return node;
}

std::vector<int> threadedInorder(ThreadedNode* root) {
    std::vector<int> result;
    if (!root) return result;
    ThreadedNode* node = leftmost(root);
    while (node) {
        result.push_back(node->val);
        if (node->rightThread) {
            node = node->right;
        } else {
            node = node->right ? leftmost(node->right) : nullptr;
        }
    }
    return result;
}

int main() {
    ThreadedNode* root = new ThreadedNode(3);
    root->left = new ThreadedNode(1);
    root->left->right = new ThreadedNode(2);
    root->right = new ThreadedNode(4);

    ThreadedNode* prev = nullptr;
    createThreads(root, prev);

    std::vector<int> order = threadedInorder(root);
    std::cout << "Threaded Inorder: ";
    for (size_t i = 0; i < order.size(); i++) {
        std::cout << order[i] << (i + 1 < order.size() ? ", " : "\n");
    }
    // Threaded Inorder: 1, 2, 3, 4
    return 0;
}

// Single Right-Threaded Binary Tree
import java.util.*;

public class ThreadedBinaryTree {
    static class ThreadedNode {
        int val;
        ThreadedNode left, right;
        boolean rightThread; // true if `right` is a thread to the inorder successor
        ThreadedNode(int val) { this.val = val; }
    }

    static void createThreads(ThreadedNode node, ThreadedNode[] prev) {
        if (node == null) return;
        createThreads(node.left, prev);
        if (prev[0] != null && prev[0].right == null) {
            prev[0].right = node;
            prev[0].rightThread = true;
        }
        prev[0] = node;
        createThreads(node.right, prev);
    }

    static ThreadedNode leftmost(ThreadedNode node) {
        while (node != null && node.left != null) node = node.left;
        return node;
    }

    static List<Integer> threadedInorder(ThreadedNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        ThreadedNode node = leftmost(root);
        while (node != null) {
            result.add(node.val);
            if (node.rightThread) {
                node = node.right;
            } else {
                node = (node.right != null) ? leftmost(node.right) : null;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        ThreadedNode root = new ThreadedNode();
        root.val = 3;
        root.left = new ThreadedNode();
        root.left.val = 1;
        root.left.right = new ThreadedNode();
        root.left.right.val = 2;
        root.right = new ThreadedNode();
        root.right.val = 4;

        createThreads(root, new ThreadedNode[]{null});
        System.out.println("Threaded Inorder: " + threadedInorder(root)); // [1, 2, 3, 4]
    }
}

6. Boundary Traversal

Boundary traversal returns only the outline of a tree: the root, the left boundary read top-down, every leaf read left-to-right, and the right boundary read bottom-up. It is assembled from three separate walks that never overlap, so no node is ever emitted twice:

Left boundary (top-down, excluding leaves): start at root.left; at each step, record the node unless it is a leaf, then move to its left child if one exists, otherwise its right child.
All leaves (left to right): a plain DFS over the whole tree that records only nodes with no children.
Right boundary (bottom-up, excluding leaves): the mirror image of step 1 starting at root.right, collected into a temporary list and reversed before appending.

# Boundary Traversal (anticlockwise outline) - O(n) time, O(h) space

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_leaf(node):
    return node is not None and node.left is None and node.right is None

def add_leaves(node, result):
    if node is None:
        return
    if is_leaf(node):
        result.append(node.val)
        return
    add_leaves(node.left, result)
    add_leaves(node.right, result)

def boundary_traversal(root):
    if root is None:
        return []
    result = [root.val]
    if is_leaf(root):
        return result

    # Left boundary, top-down, excluding leaves
    node = root.left
    while node:
        if not is_leaf(node):
            result.append(node.val)
        node = node.left if node.left else node.right

    # All leaves, left to right
    add_leaves(root.left, result)
    add_leaves(root.right, result)

    # Right boundary, bottom-up, excluding leaves
    right_boundary = []
    node = root.right
    while node:
        if not is_leaf(node):
            right_boundary.append(node.val)
        node = node.right if node.right else node.left
    result.extend(reversed(right_boundary))

    return result

# Test:      1
#          /   \
#         2     3
#        / \      \
#       4   5      6
#          / \    / \
#         7   8  9  10
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)
root.left.right.left = TreeNode(7)
root.left.right.right = TreeNode(8)
root.right.right.left = TreeNode(9)
root.right.right.right = TreeNode(10)

print("Boundary:", boundary_traversal(root))  # Boundary: [1, 2, 4, 7, 8, 9, 10, 6, 3]

// Boundary Traversal (anticlockwise outline) - O(n) time, O(h) space
#include <iostream>
#include <vector>
#include <algorithm>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

bool isLeaf(TreeNode* node) {
    return node && !node->left && !node->right;
}

void addLeaves(TreeNode* node, std::vector<int>& result) {
    if (!node) return;
    if (isLeaf(node)) {
        result.push_back(node->val);
        return;
    }
    addLeaves(node->left, result);
    addLeaves(node->right, result);
}

std::vector<int> boundaryTraversal(TreeNode* root) {
    std::vector<int> result;
    if (!root) return result;
    result.push_back(root->val);
    if (isLeaf(root)) return result;

    TreeNode* node = root->left;
    while (node) {
        if (!isLeaf(node)) result.push_back(node->val);
        node = node->left ? node->left : node->right;
    }

    addLeaves(root->left, result);
    addLeaves(root->right, result);

    std::vector<int> rightBoundary;
    node = root->right;
    while (node) {
        if (!isLeaf(node)) rightBoundary.push_back(node->val);
        node = node->right ? node->right : node->left;
    }
    std::reverse(rightBoundary.begin(), rightBoundary.end());
    result.insert(result.end(), rightBoundary.begin(), rightBoundary.end());

    return result;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);
    root->left->right->left = new TreeNode(7);
    root->left->right->right = new TreeNode(8);
    root->right->right->left = new TreeNode(9);
    root->right->right->right = new TreeNode(10);

    std::vector<int> boundary = boundaryTraversal(root);
    std::cout << "Boundary: ";
    for (size_t i = 0; i < boundary.size(); i++) {
        std::cout << boundary[i] << (i + 1 < boundary.size() ? ", " : "\n");
    }
    // Boundary: 1, 2, 4, 7, 8, 9, 10, 6, 3
    return 0;
}

// Boundary Traversal (anticlockwise outline) - O(n) time, O(h) space
import java.util.*;

public class BoundaryTraversal {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    static boolean isLeaf(TreeNode node) {
        return node != null && node.left == null && node.right == null;
    }

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

    static List<Integer> boundaryTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        result.add(root.val);
        if (isLeaf(root)) return result;

        TreeNode node = root.left;
        while (node != null) {
            if (!isLeaf(node)) result.add(node.val);
            node = (node.left != null) ? node.left : node.right;
        }

        addLeaves(root.left, result);
        addLeaves(root.right, result);

        List<Integer> rightBoundary = new ArrayList<>();
        node = root.right;
        while (node != null) {
            if (!isLeaf(node)) rightBoundary.add(node.val);
            node = (node.right != null) ? node.right : node.left;
        }
        Collections.reverse(rightBoundary);
        result.addAll(rightBoundary);

        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(8);
        root.right.right.left = new TreeNode(9);
        root.right.right.right = new TreeNode(10);

        System.out.println("Boundary: " + boundaryTraversal(root)); // [1, 2, 4, 7, 8, 9, 10, 6, 3]
    }
}

7. Serialization and Deserialization (LeetCode 297)

Serialization converts a tree into a string that can be stored or transmitted; deserialization rebuilds the exact same tree from that string. The simplest correct scheme is preorder traversal with explicit null markers: every node, including a null child, is written; on the way back in, a recursive reader consumes tokens in the same order they were written, so it always knows whether the next token is a real value or a null marker.

# Serialize / Deserialize a Binary Tree - O(n) time, O(n) space

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def serialize(root):
    vals = []
    def preorder(node):
        if node is None:
            vals.append('#')
        else:
            vals.append(str(node.val))
            preorder(node.left)
            preorder(node.right)
    preorder(root)
    return ','.join(vals)

def deserialize(data):
    tokens = iter(data.split(','))
    def build():
        token = next(tokens)
        if token == '#':
            return None
        node = TreeNode(int(token))
        node.left = build()
        node.right = build()
        return node
    return build()

def preorder_values(node, out):
    if node is None:
        return
    out.append(node.val)
    preorder_values(node.left, out)
    preorder_values(node.right, out)

# Test:    1
#         / \
#        2   3
#       /
#      4
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)

data = serialize(root)
print("Serialized:", data)  # Serialized: 1,2,4,#,#,#,3,#,#

restored = deserialize(data)
out = []
preorder_values(restored, out)
print("Restored preorder:", out)  # Restored preorder: [1, 2, 4, 3]

// Serialize / Deserialize a Binary Tree - O(n) time, O(n) space
#include <iostream>
#include <sstream>
#include <string>
#include <vector>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void serializeHelper(TreeNode* node, std::ostringstream& out) {
    if (!node) {
        out << "#,";
        return;
    }
    out << node->val << ",";
    serializeHelper(node->left, out);
    serializeHelper(node->right, out);
}

std::string serialize(TreeNode* root) {
    std::ostringstream out;
    serializeHelper(root, out);
    return out.str();
}

TreeNode* deserializeHelper(std::istringstream& in) {
    std::string token;
    std::getline(in, token, ',');
    if (token.empty() || token == "#") return nullptr;
    TreeNode* node = new TreeNode(std::stoi(token));
    node->left = deserializeHelper(in);
    node->right = deserializeHelper(in);
    return node;
}

TreeNode* deserialize(const std::string& data) {
    std::istringstream in(data);
    return deserializeHelper(in);
}

void preorderValues(TreeNode* node, std::vector<int>& out) {
    if (!node) return;
    out.push_back(node->val);
    preorderValues(node->left, out);
    preorderValues(node->right, out);
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);

    std::string data = serialize(root);
    std::cout << "Serialized: " << data << std::endl;
    // Serialized: 1,2,4,#,#,#,3,#,#,

    TreeNode* restored = deserialize(data);
    std::vector<int> order;
    preorderValues(restored, order);
    std::cout << "Restored preorder: ";
    for (size_t i = 0; i < order.size(); i++) {
        std::cout << order[i] << (i + 1 < order.size() ? ", " : "\n");
    }
    // Restored preorder: 1, 2, 4, 3
    return 0;
}

// Serialize / Deserialize a Binary Tree - O(n) time, O(n) space
import java.util.*;

public class TreeSerializer {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    static String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serializeHelper(root, sb);
        return sb.toString();
    }

    private static void serializeHelper(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("#,");
            return;
        }
        sb.append(node.val).append(",");
        serializeHelper(node.left, sb);
        serializeHelper(node.right, sb);
    }

    static TreeNode deserialize(String data) {
        Deque<String> tokens = new ArrayDeque<>(Arrays.asList(data.split(",")));
        return deserializeHelper(tokens);
    }

    private static TreeNode deserializeHelper(Deque<String> tokens) {
        String token = tokens.poll();
        if (token == null || token.equals("#")) return null;
        TreeNode node = new TreeNode(Integer.parseInt(token));
        node.left = deserializeHelper(tokens);
        node.right = deserializeHelper(tokens);
        return node;
    }

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

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);

        String data = serialize(root);
        System.out.println("Serialized: " + data);
        // Serialized: 1,2,4,#,#,#,3,#,#,

        TreeNode restored = deserialize(data);
        List<Integer> order = new ArrayList<>();
        preorderValues(restored, order);
        System.out.println("Restored preorder: " + order); // [1, 2, 4, 3]
    }
}

Tracing the deserializer over the token stream 1,2,4,#,#,#,3,#,# shows exactly how the recursive reader rebuilds the tree one token at a time:

Step	Token consumed	Action	Node built
1	"1"	Not '#' → create node, then recurse for its left subtree	Node(1)
2	"2"	Not '#' → create node, recurse for its left subtree	Node(2), 1.left = Node(2)
3	"4"	Not '#' → create node, recurse for its left subtree	Node(4), 2.left = Node(4)
4	"#"	Null marker → 4.left = None	—
5	"#"	Null marker → 4.right = None	—
6	"#"	Null marker → 2.right = None (2 is fully built)	—
7	"3"	Not '#' → create node; this becomes 1.right	Node(3), 1.right = Node(3)
8	"#"	Null marker → 3.left = None	—
9	"#"	Null marker → 3.right = None (tree fully built)	—

8. Complexity Analysis

Morris inorder/preorder: $O(n)$ time — each edge in the tree is traversed at most twice (once to create/find a thread, once to remove it) — and $O(1)$ extra space, versus $O(n)$ space for a stack-based iterative traversal or $O(h)$ call-stack space for a recursive one.

Threaded trees: $O(n)$ traversal time and $O(1)$ extra space per traversal once threads exist. Construction is a one-time $O(n)$ pass that uses $O(h)$ recursion-stack space.

Boundary traversal: $O(n)$ time — the left boundary, leaves, and right boundary walks together visit each node a constant number of times — and $O(h)$ space for the leaf-collecting recursion.

Serialization/deserialization: $O(n)$ time and $O(n)$ space for both directions — every node (and every null child) contributes exactly one token to the string, and the recursion depth is $O(h)$.

9. Applications and Alternatives

Where these techniques show up in practice

Morris traversal: memory-constrained environments (embedded systems, kernel code) where allocating a stack or recursing is undesirable, and any setting that needs traversal without disturbing the call stack's depth budget.
Threaded trees: classic technique from early compiler symbol tables and iterator implementations that needed cheap, repeated traversal without stack overhead; still relevant wherever a tree is built once and walked many times.
Boundary traversal: rendering the silhouette/outline of a hierarchical structure (LeetCode 545), UI tree visualizations, and any "draw just the perimeter" task.
Serialization: persisting trees to disk or a database, sending them across a network (RPC/API payloads), snapshotting expected values in tests, and caching parsed expression trees in compilers and query engines.

The stack-based (or recursive) traversals from Part 9 remain the right default when extra space is not a constraint — they are simpler to read and debug. Reach for Morris traversal or a threaded tree specifically when the $O(1)$-space guarantee matters. For serialization at scale, purpose-built formats like Protocol Buffers or JSON schemas replace the hand-rolled preorder-with-nulls string, trading a larger dependency for cross-language compatibility and schema evolution.

10. Exercises

Easy

Count the number of nodes in a tree using Morris traversal, without any extra data structure beyond the fixed pointer variables the traversal already uses.
Modify Morris inorder traversal to return the $k$-th smallest value in a BST without collecting the full result list.

Medium

Design a serializer/deserializer specifically for a binary search tree. Because a BST's inorder sequence is always sorted, a plain preorder listing of values (with no null markers at all) is sufficient to reconstruct the tree: rebuild recursively by tracking a valid value range for each subtree, using the BST property instead of an explicit marker to know where each subtree ends. Compare the resulting string length against the null-marker scheme from Section 7.
Extend the single right-threaded tree from Section 5 into a double-threaded tree (both left and right null pointers become threads), and implement a reverse (right-to-left) traversal that uses the left threads.

Hard

Run the boundary traversal from Section 6 on a tree that has duplicate values (for example, several nodes holding the value 5). Confirm, by tracing the algorithm, that it still produces the correct outline, and explain in one sentence why: the walk is driven entirely by node references and structure (left/right pointers, leaf tests), never by comparing values, so duplicate values cannot cause a node to be skipped or double-counted.
Design a serialization scheme for a tree whose nodes can have an arbitrary number of children (an N-ary tree) rather than exactly two. One approach: serialize each node as its value followed by its child count, then recursively serialize each child; deserialize by reading the count first so the reader always knows how many children to expect.

Mastery challenge: A production service must expose a REST endpoint that returns a binary tree's outline (its boundary) and must be able to persist/restore the full tree between deploys with zero data loss. Implement both boundary traversal and serialization/deserialization from scratch without notes, verify the serializer round-trips a tree with at least one null child at every level, and state which of the two operations would break first if the tree were mutated concurrently by another thread.

Review rhythm: tomorrow, re-derive Morris inorder traversal from the core insight alone, without looking at the code. Next week, implement Morris preorder, the threaded tree, boundary traversal, and the serializer in a single sitting, timing yourself. Several weeks later, apply the "repurpose a null pointer" idea to a new problem you have not seen before, and teach the difference between a temporary thread (Morris) and a permanent thread (threaded tree) to someone who already knows recursive traversal.

11. Summary Cheat Sheet

Morris inorder traversal threads a node's inorder predecessor to itself temporarily, traverses in $O(n)$ time and $O(1)$ space, then removes the thread to restore the tree.
Morris preorder is Morris inorder with one line moved: visit the node when its thread is created, not when it is removed.
Threaded binary trees make Morris's temporary threads permanent, trading a per-node flag for stack-free traversal on every future pass; single-threaded trees thread only the right pointers, double-threaded trees thread both.
Boundary traversal assembles the root, the left spine (excluding leaves, top-down), all leaves (left to right), and the right spine (excluding leaves, reversed to read bottom-up) — three non-overlapping walks, $O(n)$ time.
Preorder-with-null-markers serialization (LeetCode 297) round-trips any binary tree exactly in $O(n)$ time and space; a BST can drop the null markers entirely by using value ranges during reconstruction.
Zigzag level order, vertical order traversal, and traversal-pair reconstruction (preorder+inorder, inorder+postorder) live in Part 9, not here.

Cookie Consent

Advanced Tree Traversal: Morris, Threaded Trees & Serialization

Table of Contents

1. Introduction & Motivation

2. Prerequisites

3. Morris Inorder Traversal

Trace Morris inorder on a 5-node tree

4. Morris Preorder Traversal

5. Threaded Binary Trees

6. Boundary Traversal

7. Serialization and Deserialization (LeetCode 297)

8. Complexity Analysis

9. Applications and Alternatives

Where these techniques show up in practice

10. Exercises

Easy

Medium

Hard

11. Summary Cheat Sheet

Cookie Consent

Advanced Tree Traversal: Morris, Threaded Trees & Serialization

Table of Contents

1. Introduction & Motivation

2. Prerequisites

3. Morris Inorder Traversal

Trace Morris inorder on a 5-node tree

4. Morris Preorder Traversal

5. Threaded Binary Trees

6. Boundary Traversal

7. Serialization and Deserialization (LeetCode 297)

8. Complexity Analysis

9. Applications and Alternatives

Where these techniques show up in practice

10. Exercises

Easy

Medium

Hard

11. Summary Cheat Sheet

Continue the DSA Curriculum

Data Structures & Algorithms Hub

Part 9: Complete DSA Series - Trees

Part 10: BST & Balanced Trees