Level Order Traversal Appraoch

Key steps for inversion using level order traversal:

1. Enqueue the root node
2. Swap left and right chidlren of the dequeued node
3. Enqueue non-null children for further processing

void invertViaLevelOrder(Node* root) {
    if (!root) return;
    
    queue<Node*> q;
    q.push(root);
    
    while (!q.empty()) {
        Node* current = q.front();
        q.pop();
        
        // Swap children
        Node* temp = current->left;
        current->left = current->right;
        current->right = temp;
        
        // Enqueue children for further processing
        if (current->left) q.push(current->left);
        if (current->right) q.push(current->right);
    }
}

Recursive Preorder Approach

Recursive method for tree inversion:

1. Base case: return if node is null
2. Swap left and right children
3. Recursive invert left and right subtrees

void invertRecursive(Node* node) {
    if (!node) return;
    
    // Swap children
    Node* temp = node->left;
    node->left = node->right;
    node->right = temp;
    
    // Recursively process subtrees
    invertRecursive(node->left);
    invertRecursive(node->right);
}

Implementation Example

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

int main() {
    // Build sample tree
    Node* root = new Node(6);
    root->left = new Node(3);
    root->right = new Node(9);
    root->left->left = new Node(1);
    root->left->right = new Node(4);
    root->right->left = new Node(8);
    root->left->left->left = new Node(0);
    
    // Invert tree
    invertRecursive(root);
    
    // Output inverted tree (level order)
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* current = q.front();
        q.pop();
        cout << current->data << " ";
        if (current->left) q.push(current->left);
        if (current->right) q.push(current->right);
    }
}