Binary Tree: Given a binary tree, invert it

Problem Statement

Given a binary tree, invert it

Example:

Input:

    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */

Output:

    /*
     *           10
     *         /    \
     *        12     8
     *       / \    /  \
     *     14   11  9   2
     */

Solution Explanation:

We will use iterative DFS approach.

We will use stack to solve the problem.

We will insert root into the stack, keep swapping the elements to arrive at the solution.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

struct Node 
{
    int data;
    struct Node *left;
    struct Node *right;
};


struct Node* newNode(int data)
{
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;

    return (newNode);
}

void display_inorder(Node* root)
{
    if (root == NULL)
        return;

    display_inorder(root->left);
    cout << root->data << " ";
    display_inorder(root->right);
}


void insert_inorder(Node* root, vector<int>& nodes) 
{
    if (root == nullptr) 
    {
        return;
    }
  
    insert_inorder(root->left, nodes);  
    nodes.push_back(root->data);          
    insert_inorder(root->right, nodes); 
}

Node* solution(Node* root) 
{
    std::stack<Node*> stk;
    stk.push(root);
    
    while (!stk.empty()) 
    {
        Node* p = stk.top();
        stk.pop();

        if (p) 
        {
            stk.push(p->left);
            stk.push(p->right);
            std::swap(p->left, p->right);
        }
    }
    return root;
}

int main(void)
{
    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */
    struct Node* root = newNode(10);
    root->left = newNode(8);
    root->right = newNode(12);
    root->left->left = newNode(2);
    root->left->right = newNode(9);
    root->right->left = newNode(11);
    root->right->right = newNode(14);

    solution(root);
    
    cout << "Inorder traversal : ";
    display_inorder(root);
    return 0;
}

Output

Inorder traversal : 14 12 11 10 9 8 2