Tree Traversal

1. Inorder Morris Traversal O(1) Space

Concept	Strategy	Time	Space
Threaded Binary Tree	Create temporary links from predecessor to current node	`O(n)`	`O(1)`
Predecessor Finding	For current node, find rightmost node in left subtree	`O(1)` amortized	No stack needed
Link Creation	Make predecessor's right child point to current (thread)	Temporary modification	Restored after use
Link Removal	Remove thread after visiting, restore original structure	Tree unchanged	No permanent changes

Example: Morris inorder traversal

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function morrisInorder(root) {
    const result = [];
    let curr = root;
    
    while (curr !== null) {
        if (curr.left === null) {
            // No left subtree, visit and go right
            result.push(curr.val);
            curr = curr.right;
        } else {
            // Find inorder predecessor
            let pred = curr.left;
            while (pred.right !== null && pred.right !== curr) {
                pred = pred.right;
            }
            
            if (pred.right === null) {
                // Create thread
                pred.right = curr;
                curr = curr.left;
            } else {
                // Thread exists, remove it and visit
                pred.right = null;
                result.push(curr.val);
                curr = curr.right;
            }
        }
    }
    
    return result;
}

// Example tree:     4
//                  / \
//                 2   6
//                / \ / \
//               1  3 5  7
// Inorder: [1, 2, 3, 4, 5, 6, 7]

Note: Morris traversal is O(1) space by using threaded links. Each edge is traversed at most 3 times: once going down, once creating thread, once removing thread. Still O(n) time overall.

Example: Morris preorder and postorder

// Morris Preorder: Visit before going left
function morrisPreorder(root) {
    const result = [];
    let curr = root;
    
    while (curr !== null) {
        if (curr.left === null) {
            result.push(curr.val);
            curr = curr.right;
        } else {
            let pred = curr.left;
            while (pred.right !== null && pred.right !== curr) {
                pred = pred.right;
            }
            
            if (pred.right === null) {
                result.push(curr.val); // Visit before thread
                pred.right = curr;
                curr = curr.left;
            } else {
                pred.right = null;
                curr = curr.right;
            }
        }
    }
    
    return result;
}

// Morris Postorder is more complex
// Requires reversing right spine of left subtrees
function morrisPostorder(root) {
    const dummy = new TreeNode(0);
    dummy.left = root;
    const result = [];
    let curr = dummy;
    
    while (curr !== null) {
        if (curr.left === null) {
            curr = curr.right;
        } else {
            let pred = curr.left;
            while (pred.right !== null && pred.right !== curr) {
                pred = pred.right;
            }
            
            if (pred.right === null) {
                pred.right = curr;
                curr = curr.left;
            } else {
                // Reverse and visit right spine
                reverseAddNodes(curr.left, pred, result);
                pred.right = null;
                curr = curr.right;
            }
        }
    }
    
    return result;
}

function reverseAddNodes(from, to, result) {
    reverse(from, to);
    let node = to;
    while (true) {
        result.push(node.val);
        if (node === from) break;
        node = node.right;
    }
    reverse(to, from);
}

2. Level Order Bottom Up

Approach	Method	Data Structure	Complexity
BFS + Reverse	Standard level order, then reverse result array	Queue + array	`O(n)` time, `O(n)` space
BFS + Stack	Use stack to reverse levels as we go	Queue + stack	`O(n)` time, `O(n)` space
DFS + Level Tracking	Track depth, insert at beginning of level arrays	Array of arrays	`O(n)` time, `O(h)` recursion
Two Queue	Process level by level with two queues	Two queues	`O(n)` time, `O(w)` width

Example: Bottom-up level order (BFS + reverse)

function levelOrderBottom(root) {
    if (!root) return [];
    
    const result = [];
    const queue = [root];
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        const level = [];
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            level.push(node.val);
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        result.push(level);
    }
    
    return result.reverse();
}

// Example tree:     3
//                  / \
//                 9  20
//                   /  \
//                  15   7
// Result: [[15,7], [9,20], [3]]

Example: Bottom-up using DFS

function levelOrderBottomDFS(root) {
    const result = [];
    
    function dfs(node, level) {
        if (!node) return;
        
        // Ensure array exists for this level
        if (result.length === level) {
            result.push([]);
        }
        
        result[level].push(node.val);
        
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
    
    dfs(root, 0);
    return result.reverse();
}

// Alternative: Insert at beginning
function levelOrderBottomDFS2(root) {
    const result = [];
    
    function dfs(node, level) {
        if (!node) return;
        
        if (result.length === level) {
            result.unshift([]); // Insert at beginning
        }
        
        result[result.length - 1 - level].push(node.val);
        
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
    
    dfs(root, 0);
    return result;
}

3. Vertical Order Traversal

Concept	Technique	Sorting Criteria	Use Case
Column Indexing	Assign column index: left child = col-1, right child = col+1	Primary: column	Group nodes by vertical position
Row Tracking	Track row (level/depth) for each node	Secondary: row	Order within same column
Value Sorting	Sort by value when col and row are same	Tertiary: value	Deterministic ordering
Map Storage	Use map with column as key, array of (row, val) as value	Efficient grouping	Collect all nodes per column

Example: Vertical order traversal with sorting

function verticalTraversal(root) {
    if (!root) return [];
    
    const map = new Map(); // col -> [[row, val], ...]
    let minCol = 0, maxCol = 0;
    
    // BFS with (node, row, col) tuples
    const queue = [[root, 0, 0]];
    
    while (queue.length > 0) {
        const [node, row, col] = queue.shift();
        
        if (!map.has(col)) {
            map.set(col, []);
        }
        map.get(col).push([row, node.val]);
        
        minCol = Math.min(minCol, col);
        maxCol = Math.max(maxCol, col);
        
        if (node.left) {
            queue.push([node.left, row + 1, col - 1]);
        }
        if (node.right) {
            queue.push([node.right, row + 1, col + 1]);
        }
    }
    
    const result = [];
    
    // Process columns from left to right
    for (let col = minCol; col <= maxCol; col++) {
        const column = map.get(col);
        
        // Sort by row, then by value
        column.sort((a, b) => {
            if (a[0] !== b[0]) return a[0] - b[0]; // row
            return a[1] - b[1]; // value
        });
        
        result.push(column.map(item => item[1]));
    }
    
    return result;
}

// Example tree:      3
//                   / \
//                  9  20
//                    /  \
//                   15   7
// Result: [[9], [3,15], [20], [7]]

4. Boundary Traversal Pattern

Boundary Part	Traversal	Direction	Exclusions
Left Boundary	Root to leftmost leaf (excluding leaf)	Top to bottom	Don't include leaf nodes
Leaves	All leaf nodes from left to right	Left to right	Inorder/preorder traversal
Right Boundary	Rightmost leaf to root (excluding root and leaf)	Bottom to top	Process in reverse
Root Handling	Add root first if not a leaf	Special case	Avoid duplicates

Example: Binary tree boundary traversal

function boundaryOfBinaryTree(root) {
    if (!root) return [];
    
    const result = [];
    
    // Add root if not a leaf
    if (!isLeaf(root)) {
        result.push(root.val);
    }
    
    // Add left boundary (top to bottom, excluding leaves)
    let node = root.left;
    while (node) {
        if (!isLeaf(node)) {
            result.push(node.val);
        }
        node = node.left ? node.left : node.right;
    }
    
    // Add all leaves (left to right)
    addLeaves(root, result);
    
    // Add right boundary (bottom to top, excluding leaves)
    const rightBoundary = [];
    node = root.right;
    while (node) {
        if (!isLeaf(node)) {
            rightBoundary.push(node.val);
        }
        node = node.right ? node.right : node.left;
    }
    
    // Reverse right boundary
    result.push(...rightBoundary.reverse());
    
    return result;
}

function isLeaf(node) {
    return node && !node.left && !node.right;
}

function addLeaves(node, result) {
    if (!node) return;
    
    if (isLeaf(node)) {
        result.push(node.val);
        return;
    }
    
    addLeaves(node.left, result);
    addLeaves(node.right, result);
}

// Example tree:       1
//                   /   \
//                  2     3
//                 / \   / 
//                4   5 6   
//               / \   /
//              7   8 9
// Boundary: [1, 2, 4, 7, 8, 9, 6, 3]

5. Zigzag Level Order

Approach	Method	Reversal Strategy	Complexity
BFS + Reverse Alternate	Normal BFS, reverse every other level	Reverse array after level completion	`O(n)`
Deque	Use deque, alternate between addFirst/addLast	Add to appropriate end based on level	`O(n)`
Two Stacks	Alternate between two stacks for levels	Stack naturally reverses order	`O(n)`
DFS + Level Flag	Track level, insert at appropriate position	Insert at beginning or end based on parity	`O(n)`

Example: Zigzag with BFS and reverse

function zigzagLevelOrder(root) {
    if (!root) return [];
    
    const result = [];
    const queue = [root];
    let leftToRight = true;
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        const level = [];
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            level.push(node.val);
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        // Reverse if right to left
        if (!leftToRight) {
            level.reverse();
        }
        
        result.push(level);
        leftToRight = !leftToRight;
    }
    
    return result;
}

// Example:      3
//              / \
//             9  20
//               /  \
//              15   7
// Result: [[3], [20,9], [15,7]]

Example: Zigzag with two stacks

function zigzagLevelOrderStacks(root) {
    if (!root) return [];
    
    const result = [];
    let currLevel = [root];
    let nextLevel = [];
    let leftToRight = true;
    let level = [];
    
    while (currLevel.length > 0) {
        const node = currLevel.pop();
        level.push(node.val);
        
        if (leftToRight) {
            if (node.left) nextLevel.push(node.left);
            if (node.right) nextLevel.push(node.right);
        } else {
            if (node.right) nextLevel.push(node.right);
            if (node.left) nextLevel.push(node.left);
        }
        
        if (currLevel.length === 0) {
            result.push(level);
            level = [];
            [currLevel, nextLevel] = [nextLevel, currLevel];
            leftToRight = !leftToRight;
        }
    }
    
    return result;
}

// Uses stack property: last pushed is first popped
// Alternates child order to achieve zigzag

6. Serialize Deserialize Tree

Format	Encoding	Decoding	Features
Preorder with Nulls	Preorder traversal, mark nulls explicitly	Reconstruct using preorder pattern	Simple, unambiguous
Level Order BFS	Level by level, include nulls	Rebuild level by level with queue	Natural representation
Parenthesis Notation	val(left)(right) format	Parse recursively	Human readable
Compact Binary	Use null markers, skip nulls where possible	Requires careful parsing	Space efficient

Example: Serialize/deserialize with preorder

class Codec {
    serialize(root) {
        const result = [];
        
        function preorder(node) {
            if (!node) {
                result.push("null");
                return;
            }
            result.push(node.val.toString());
            preorder(node.left);
            preorder(node.right);
        }
        
        preorder(root);
        return result.join(",");
    }
    
    deserialize(data) {
        const values = data.split(",");
        let index = 0;
        
        function buildTree() {
            if (values[index] === "null") {
                index++;
                return null;
            }
            
            const node = new TreeNode(
                parseInt(values[index++])
            );
            node.left = buildTree();
            node.right = buildTree();
            return node;
        }
        
        return buildTree();
    }
}

// Example: Tree [1,2,3,null,null,4,5]
// Serialized: "1,2,null,null,3,4,null,null,5,null,null"

Example: Serialize/deserialize with BFS

class CodecBFS {
    serialize(root) {
        if (!root) return "";
        
        const result = [];
        const queue = [root];
        
        while (queue.length > 0) {
            const node = queue.shift();
            
            if (node) {
                result.push(node.val);
                queue.push(node.left);
                queue.push(node.right);
            } else {
                result.push("null");
            }
        }
        
        return result.join(",");
    }
    
    deserialize(data) {
        if (!data) return null;
        
        const values = data.split(",");
        const root = new TreeNode(
            parseInt(values[0])
        );
        const queue = [root];
        let i = 1;
        
        while (queue.length > 0) {
            const node = queue.shift();
            
            // Left child
            if (values[i] !== "null") {
                node.left = new TreeNode(
                    parseInt(values[i])
                );
                queue.push(node.left);
            }
            i++;
            
            // Right child
            if (values[i] !== "null") {
                node.right = new TreeNode(
                    parseInt(values[i])
                );
                queue.push(node.right);
            }
            i++;
        }
        
        return root;
    }
}

// Level order format is more intuitive
// Matches typical tree diagram representation

Note: For serialization:

Preorder: Most compact recursive solution, easy to implement
Level order: Matches visual representation, easier to debug
Always mark nulls: Essential for unambiguous reconstruction
Choose delimiter wisely: Avoid conflicts with node values (use comma, pipe, etc.)

Summary: Tree Traversal Patterns

Morris Traversal: O(1) space inorder/preorder using threaded binary tree - create temporary links to predecessors, visit, then remove links
Predecessor Finding: For node N, predecessor is rightmost node in left subtree - enables threading without stack
Level Order Bottom-Up: Standard BFS then reverse, or DFS with level tracking and reverse insertion
Vertical Order: Assign column indices (left=-1, right=+1), track row, sort by (col, row, val) - use BFS with tuples
Boundary Traversal: Three parts: left boundary (top-down), leaves (left-right), right boundary (bottom-up reversed)
Zigzag Level Order: BFS with alternating reversal, or two stacks alternating child order, or deque with directional insertion
Serialization: Preorder with null markers (compact recursive) or level order (intuitive iterative) - always mark nulls explicitly
Deserialization: Preorder uses recursion with index tracking; level order uses queue with parent-child linking
Space Optimization: Morris O(1) for traversal, iterative for level order O(width), recursive uses O(height) stack
Common Patterns: BFS for level-based, DFS for depth-based, threading for space optimization, queue/stack for order control

Related Cheatsheets

Datastructures-algorithms