Pre Order Traversal - Comprehensive Concept Content

Overview

Pre-order traversal is a fundamental tree traversal algorithm where nodes are visited in the order: Root → Left Subtree → Right Subtree. This traversal pattern is particularly useful for creating a copy of the tree, expressing arithmetic expressions in prefix notation, and reconstructing trees from traversal sequences.

Key Properties

1. Visit Order: Root node is processed before its children
2. Recursive Nature: Natural fit for recursive implementations
3. Expression Evaluation: Used in prefix notation evaluation
4. Tree Reconstruction: Essential for building trees from traversal data

Algorithm Implementation

Recursive Approach

// Pre-order traversal - Recursive
function preOrderTraversal(root) {
    const result = [];
    
    function traverse(node) {
        if (!node) return;
        
        // Process root first
        result.push(node.val);
        
        // Traverse left subtree
        traverse(node.left);
        
        // Traverse right subtree
        traverse(node.right);
    }
    
    traverse(root);
    return result;
}

Iterative Approach

// Pre-order traversal - Iterative
function preOrderTraversalIterative(root) {
    if (!root) return [];
    
    const result = [];
    const stack = [root];
    
    while (stack.length > 0) {
        const node = stack.pop();
        result.push(node.val);
        
        // Push right child first (so left is processed first)
        if (node.right) {
            stack.push(node.right);
        }
        
        if (node.left) {
            stack.push(node.left);
        }
    }
    
    return result;
}

Morris Traversal (Threaded Approach)

// Pre-order traversal - Morris Traversal
function morrisPreOrder(root) {
    const result = [];
    let current = root;
    
    while (current) {
        if (!current.left) {
            // Process current node
            result.push(current.val);
            current = current.right;
        } else {
            // Find inorder predecessor
            let predecessor = current.left;
            while (predecessor.right && predecessor.right !== current) {
                predecessor = predecessor.right;
            }
            
            if (!predecessor.right) {
                // Make current as right child of predecessor
                result.push(current.val); // Process root
                predecessor.right = current;
                current = current.left;
            } else {
                // Revert the changes
                predecessor.right = null;
                current = current.right;
            }
        }
    }
    
    return result;
}

Step-by-Step Example

Consider this binary tree:

        1
       / \
      2   3
     / \
    4   5

Pre-order Traversal Process:

1. Visit Root (1) → Add 1 to result
2. Visit Left Subtree (2):

• Visit Root (2) → Add 2 to result
• Visit Left Subtree (4) → Add 4 to result
• Visit Right Subtree (5) → Add 5 to result

1. Visit Right Subtree (3) → Add 3 to result

Final Result: [1, 2, 4, 5, 3]

Time and Space Complexity

| Aspect | Time Complexity | Space Complexity |

|--------|---------------|--------------|

| Best Case | O(n) | O(h) |

| Average Case | O(n) | O(h) |

| Worst Case | O(n) | O(h) |

Where:

• n = number of nodes in the tree
• h = height of the tree (h = log n for balanced trees, h = n for skewed trees)

Space Complexity Analysis:

• Recursive: O(h) - due to call stack
• Iterative: O(h) - due to explicit stack storage
• Morris: O(1) - no extra space (but modifies tree temporarily)

Applications

1. Tree Copying/Cloning

// Create a deep copy of tree using pre-order traversal
function cloneTree(root) {
    if (!root) return null;
    
    const newNode = new TreeNode(root.val);
    newNode.left = cloneTree(root.left);
    newNode.right = cloneTree(root.right);
    
    return newNode;
}

2. Expression Tree Evaluation

For arithmetic expressions in prefix notation:

    +
   / \
  *   -
 / \ / \
a b c d

Prefix Expression: + * a b - c d

3. Serialization/Deserialization

// Serialize tree using pre-order traversal
function serialize(root) {
    const result = [];
    
    function preorder(node) {
        if (!node) {
            result.push('null');
            return;
        }
        
        result.push(node.val);
        preorder(node.left);
        preorder(node.right);
    }
    
    preorder(root);
    return result.join(',');
}

4. Convert to Prefix Notation

// Convert binary tree to prefix expression
function toPrefix(root) {
    if (!root) return '';
    
    const left = toPrefix(root.left);
    const right = toPrefix(root.right);
    
    if (left === '' && right === '') {
        return root.val;
    }
    
    return `${root.val} ${left} ${right}`;
}

Comparison with Other Traversals

Pre-order vs In-order vs Post-order

| Traversal | Order | Use Cases |

|-----------|---------|-----------|

| Pre-order | Root → Left → Right | Tree copying, prefix expressions |

| In-order | Left → Root → Right | Sorted output, BST validation |

| Post-order | Left → Right → Root | Tree deletion, postfix expressions |

Example Comparison

For tree:

    1
   / \
  2   3
 / \
4   5

Pre-order: [1, 2, 4, 5, 3]

In-order: [4, 2, 5, 1, 3]

Post-order: [4, 5, 2, 3, 1]

Common Variations

1. Level-order Pre-order (BFS Pre-order)

function bfsPreOrder(root) {
    if (!root) return [];
    
    const result = [];
    const queue = [root];
    
    while (queue.length > 0) {
        const node = queue.shift();
        result.push(node.val);
        
        // Add children to queue (right first, then left)
        if (node.right) {
            queue.push(node.right);
        }
        if (node.left) {
            queue.push(node.left);
        }
    }
    
    return result;
}

2. Iterative with Enhanced Control

// Pre-order traversal with custom processing
function preOrderWithProcessing(root, processCallback) {
    const stack = [root];
    
    while (stack.length > 0) {
        const node = stack.pop();
        
        if (node) {
            processCallback(node.val);
            
            // Push right first, then left (so left is processed first)
            stack.push(node.right);
            stack.push(node.left);
        }
    }
}

Performance Characteristics

Balanced vs Unbalanced Trees

Balanced Tree (Height = log n):

• Time Complexity: O(n) - Visit each node once
• Space Complexity: O(log n) - Call stack depth

Skewed Tree (Height = n):

• Time Complexity: O(n) - Still visit each node once
• Space Complexity: O(n) - Call stack depth becomes n

Memory Usage Patterns

1. Recursive:

• Stack grows linearly with tree height
• Risk of stack overflow for very deep trees

1. Iterative:

• Explicit stack management
• More predictable memory usage

1. Morris:

• O(1) extra space (temporarily modifies tree)
• No stack overhead

Common Mistakes to Avoid

1. Incorrect Order of Operations

Problem: Processing children in wrong order

// WRONG - Wrong order
function wrongPreOrder(node) {
    if (!node) return;
    
    console.log(node.val); // Process root first (CORRECT)
    wrongPreOrder(node.right); // Right before left (WRONG!)
    wrongPreOrder(node.left); // Left after right (WRONG!)
}

Solution: Process left subtree before right subtree

2. Not Handling Null Nodes Properly

// WRONG - Missing null check
function badPreOrder(node) {
    console.log(node.val); // Will throw error if node is null
    preOrder(node.left);
    preOrder(node.right);
}

// CORRECT - Proper null handling
function goodPreOrder(node) {
    if (!node) return;
    
    console.log(node.val);
    goodPreOrder(node.left);
    goodPreOrder(node.right);
}

3. Stack Management Errors

// WRONG - Wrong stack order
function wrongIterative(node) {
    const stack = [node];
    
    while (stack.length > 0) {
        const current = stack.pop();
        
        // Wrong order - processing right before left
        if (current.right) {
            stack.push(current.right);
        }
        if (current.left) {
            stack.push(current.left);
        }
    }
}

// CORRECT - Push right first, then left
function correctIterative(node) {
    const stack = [node];
    
    while (stack.length > 0) {
        const current = stack.pop();
        
        // Push right first, then left
        if (current.right) {
            stack.push(current.right);
        }
        if (current.left) {
            stack.push(current.left);
        }
    }
}

Real-World Applications

1. File System Navigation

// Tree structure representing file system
function traverseFileSystem(root) {
    const result = [];
    
    function preOrder(node) {
        if (node.isDirectory) {
            result.push(`DIR: ${node.name}`);
        } else {
            result.push(`FILE: ${node.name}`);
        }
        
        // Process all children in pre-order
        node.children.forEach(child => {
            preOrder(child);
        });
    }
    
    preOrder(root);
    return result;
}

2. Syntax Tree Parsing

// Parse mathematical expressions using pre-order traversal
function parseExpressionTree(expression) {
    // Build tree structure first
    const tree = buildExpressionTree(expression);
    
    // Use pre-order to generate prefix notation
    return preOrderTraversal(tree);
}

3. Game Development

// Scene graph traversal in game engines
function traverseSceneGraph(node) {
    // Process node first (pre-order)
    processNode(node);
    
    // Then process children in pre-order
    node.children.forEach(child => {
        traverseSceneGraph(child);
    });
}

Testing Strategies

1. Edge Case Testing

// Test cases for pre-order traversal
function testPreOrder() {
    // Empty tree
    assert.deepStrictEqual(preOrderTraversal(null), []);
    
    // Single node
    const singleNode = new TreeNode(1);
    assert.deepStrictEqual(preOrderTraversal(singleNode), [1]);
    
    // Complete tree
    const completeTree = buildCompleteTree();
    assert.deepStrictEqual(preOrderTraversal(completeTree), [1, 2, 4, 5, 3]);
    
    // Skewed tree
    const skewedTree = buildSkewedTree();
    assert.deepStrictEqual(preOrderTraversal(skewedTree), [1, 2, 3, 4]);
}

2. Performance Testing

function performanceTest() {
    const largeTree = buildLargeTree(10000);
    
    console.time('Recursive Pre-order');
    const result1 = preOrderTraversal(largeTree);
    console.timeEnd('Recursive Pre-order');
    
    console.time('Iterative Pre-order');
    const result2 = preOrderTraversalIterative(largeTree);
    console.timeEnd('Iterative Pre-order');
    
    // Verify results match
    assert.deepStrictEqual(result1, result2);
}

Advanced Implementation Patterns

1. Generator-Based Approach

// Generator-based pre-order traversal
function* preOrderGenerator(root) {
    if (!root) return;
    
    yield root.val;
    
    yield* preOrderGenerator(root.left);
    yield* preOrderGenerator(root.right);
}

// Usage
const tree = buildSampleTree();
for (const value of preOrderGenerator(tree)) {
    console.log(value);
}

2. Functional Programming Style

// Functional approach using reduce
const preOrderFunctional = (root) => {
    const traverse = (node, acc) => {
        if (!node) return acc;
        
        acc.push(node.val);
        return traverse(node.left, traverse(node.right, acc));
    };
    
    return traverse(root, []);
};

3. Custom Iterator Implementation

class PreOrderIterator {
    constructor(root) {
        this.stack = [];
        if (root) {
            this.stack.push(root);
        }
    }
    
    hasNext() {
        return this.stack.length > 0;
    }
    
    next() {
        if (!this.hasNext()) return null;
        
        const node = this.stack.pop();
        // Push right first, then left
        if (node.right) {
            this.stack.push(node.right);
        }
        if (node.left) {
            this.stack.push(node.left);
        }
        
        return node.val;
    }
}

Memory Optimization Techniques

1. Tail Recursion Optimization

// Tail-recursive approach (if supported by compiler)
function preOrderTailRecursive(root, result = []) {
    if (!root) return result;
    
    result.push(root.val);
    preOrderTailRecursive(root.left, result);
    preOrderTailRecursive(root.right, result);
    
    return result;
}

2. Memory Pool Strategy

// Reuse stack objects for better memory management
class PreOrderTraversal {
    constructor() {
        this.stack = [];
    }
    
    traverse(root) {
        // Clear stack before reuse
        this.stack.length = 0;
        
        if (root) {
            this.stack.push(root);
        }
        
        const result = [];
        while (this.stack.length > 0) {
            // Process nodes...
        }
        
        return result;
    }
}