Speed:

BST Tree Traversals

In-order: O(n)Pre-order: O(n)Post-order: O(n)Level-order: O(n)

🔄Tree Traversal Methods

Left → Root → Right. Visits nodes in sorted order for BST. Used for getting sorted sequence.

Root → Left → Right. Visits root first. Used for tree copying and prefix expressions.

Left → Right → Root. Visits root last. Used for tree deletion and postfix expressions.

Breadth-first traversal. Visits level by level. Uses queue data structure.

📊In-order Traversal

In-order traversal follows the pattern: Left → Root → Right. This traversal is particularly special for Binary Search Trees because it visits nodes in sorted order. The recursive approach naturally handles the traversal by first visiting the left subtree, then processing the current node, and finally visiting the right subtree. This property makes in-order traversal perfect for retrieving data from a BST in ascending order.

// In-order: Left → Root → Right
inorderTraversal(node = this.root, result = []) {
    if (node !== null) {
        // Visit left subtree
        this.inorderTraversal(node.left, result);
        
        // Visit root
        result.push(node.data);
        
        // Visit right subtree
        this.inorderTraversal(node.right, result);
    }
    return result;
}

🎯Pre-order Traversal

Pre-order traversal follows: Root → Left → Right. By visiting the root node first, this traversal creates a natural sequence for tree reconstruction. Pre-order is commonly used for copying trees, creating backup representations, and evaluating prefix expressions. The root-first approach ensures that when rebuilding a tree, you always have the parent node available before processing its children.

// Pre-order: Root → Left → Right
preorderTraversal(node = this.root, result = []) {
    if (node !== null) {
        // Visit root
        result.push(node.data);
        
        // Visit left subtree
        this.preorderTraversal(node.left, result);
        
        // Visit right subtree
        this.preorderTraversal(node.right, result);
    }
    return result;
}

🏁Post-order Traversal

Post-order traversal follows: Left → Right → Root. This traversal processes children before their parent, making it ideal for safe tree deletion and calculating tree properties like size or height. Since children are processed first, you can safely delete or modify nodes without affecting the traversal of remaining nodes. Post-order is also used for evaluating postfix expressions and performing bottom-up computations.

// Post-order: Left → Right → Root
postorderTraversal(node = this.root, result = []) {
    if (node !== null) {
        // Visit left subtree
        this.postorderTraversal(node.left, result);
        
        // Visit right subtree
        this.postorderTraversal(node.right, result);
        
        // Visit root
        result.push(node.data);
    }
    return result;
}

🌊Level-order Traversal

Level-order traversal, also known as Breadth-First Search (BFS), visits nodes level by level from left to right. Unlike the depth-first approaches (in-order, pre-order, post-order), this traversal uses a queue data structure instead of recursion or a stack. It's particularly useful for tree printing, finding the shortest path, and determining tree width at each level. Level-order traversal provides a natural way to visualize tree structure.

// Level-order: Breadth-First Search
levelorderTraversal() {
    if (!this.root) return [];
    
    const result = [];
    const queue = [this.root];
    
    while (queue.length > 0) {
        const current = queue.shift();
        result.push(current.data);
        
        if (current.left) queue.push(current.left);
        if (current.right) queue.push(current.right);
    }
    return result;
}