# Problem Statement
Given the root node of a binary tree, swap the 'left' and 'right' children for each node. The below example shows how the mirrored binary tree should look like.

<br>

# Hint
* Depth first traversal
* Bottom up mirroring

<br>

# Try it yourself

void mirror_tree(BinaryTreeNode* root) {
  //TODO: Write - Your - Code
}

#include <iostream>
#include <vector>
#include <string>
#include <list>
#include <queue>
#include <algorithm>
#include <assert.h>
#include <time.h>
#include <fstream>
#include <sstream>
#include <limits>
#include <math.h>
#include <stack>
#include <cstdlib>
using namespace std;


struct BinaryTreeNode
{
    int data;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
    BinaryTreeNode* parent;

    // below data members used only for some of the problems
    BinaryTreeNode* next;
    int count;

    BinaryTreeNode(int d) : data(d), left(nullptr), right(nullptr), next(nullptr), parent(nullptr), count(0) {
    }
};

BinaryTreeNode* insert_bst(BinaryTreeNode* root, int d) {
  BinaryTreeNode* pNew = new BinaryTreeNode(d);
  if (root == nullptr) {
    return pNew;
  }

  BinaryTreeNode* parent = nullptr;
  BinaryTreeNode* pTemp = root;
  while (pTemp != nullptr) {
    parent = pTemp;
    if (d < pTemp->data) {
      pTemp = pTemp->left;
    } else {
      pTemp = pTemp->right;
    }
  }

  if (d < parent->data) {
    parent->left = pNew;
  } else {
    parent->right = pNew;
  }

  return root;
}

BinaryTreeNode* find_in_bst(BinaryTreeNode* root, int d) {
  if(root == nullptr)
    return nullptr;

  if(root->data == d) {
    return root;
  }
  else if( root->data > d)
  {
    return find_in_bst(root->left, d);
  }
  else
  {
    return find_in_bst(root->right,d);
  }
}

BinaryTreeNode* insert_binary_tree(BinaryTreeNode* root, int d) {
  BinaryTreeNode* pNew = new BinaryTreeNode(d);
  if (root == nullptr) {
    return pNew;
  }

  BinaryTreeNode* parent = nullptr;
  BinaryTreeNode* pTemp = root;
  while (pTemp != nullptr) {
    parent = pTemp;
    if (d < pTemp->data) {
      pTemp = pTemp->left;
    } else {
      pTemp = pTemp->right;
    }
  }

  if (rand()%2 == 0) {
    parent->left = pNew;
  }
  else {
    parent->right = pNew;
  }

  return root;
}

BinaryTreeNode* create_BinaryTree(int count) {
  BinaryTreeNode* root = nullptr;
  for (int i = 0; i < count; ++i) {
    int r = rand() % 100;
    root = insert_binary_tree(root, r);
  }
  return root;
}

void display_inorder(BinaryTreeNode* node) {
  if (node == nullptr) {
    return;
  }
  display_inorder(node->left);
  cout << node->data << ", ";
  display_inorder(node->right);
}

void get_inorder(BinaryTreeNode* node, vector<int>& output) {
  if (node == nullptr) {
    return;
  }
  get_inorder(node->left, output);
  output.push_back(node->data);
  get_inorder(node->right, output);
}

void display_preorder(BinaryTreeNode* node) {
  if (node == nullptr) {
    return;
  }
  cout << node->data << ", ";

  display_preorder(node->left);
  display_preorder(node->right);
}

void get_preorder(BinaryTreeNode* node, vector<int>& output) {
  if (node == nullptr) {
    return;
  }
  output.push_back(node->data);
  get_inorder(node->left, output);
  get_inorder(node->right, output);
}

BinaryTreeNode* create_BST(vector<int>& v) {
  BinaryTreeNode* root = nullptr;
  int count = 0;
  for (int x : v) {
    root = insert_bst(root, x);
    if (count % 50000 == 0) {
      cout << "Inserted " << count << endl;
    }
    ++count;
  }
  return root;
}

BinaryTreeNode* create_random_BST(int count) {
  BinaryTreeNode* root = nullptr;
  srand(time(NULL));
  for (int i = 0; i < count; ++i) {
      int r =  rand() % 997;
      root = insert_bst(root, r);
  }
  return root;
}

void binary_tree_to_vector_rec(BinaryTreeNode* root, vector<int>& v) {
  if (root == nullptr) {
    return;
  }

  binary_tree_to_vector_rec(root->left, v);
  v.push_back(root->data);
  binary_tree_to_vector_rec(root->right, v);
}

vector<int> binary_tree_to_vector(BinaryTreeNode* root) {
  vector<int> v;
  binary_tree_to_vector_rec(root, v);
  return v;
}

void display_level_order(BinaryTreeNode* root) {
  if (root == nullptr) {
    return;
  }

  queue<BinaryTreeNode*> q;
  q.push(root);
  q.push(nullptr);

  while (!q.empty()) {
    BinaryTreeNode* temp = q.front();
    q.pop();
    cout << temp->data << ", ";
    if (temp->left != nullptr) {
      q.push(temp->left);
    }

    if (temp->right != nullptr) {
      q.push(temp->right);
    }

    if (q.front() == nullptr) {
      cout << endl;
      q.pop();
      if (!q.empty()) {
        q.push(nullptr);
      }
    }

  }
  cout << endl;
}
string display_BT(BinaryTreeNode* root) {
  string result = "";
  if (root == nullptr) {
    return "";
  }

  queue<BinaryTreeNode*> q;
  q.push(root);
  q.push(nullptr);

  while (!q.empty()) {
    BinaryTreeNode* temp = q.front();
    q.pop();
    result += std::to_string(temp->data) +", ";
    if (temp->left != nullptr) {
      q.push(temp->left);
    }

    if (temp->right != nullptr) {
      q.push(temp->right);
    }

    if (q.front() == nullptr) {
      q.pop();
      if (!q.empty()) {
        q.push(nullptr);
      }
    }

  }
  return result;
}

void get_level_order(BinaryTreeNode* root, vector<int>& output) {
  if (root == nullptr) {
    return;
  }

  queue<BinaryTreeNode*> q;
  q.push(root);

  while (!q.empty()) {
    BinaryTreeNode* temp = q.front();
    q.pop();

    output.push_back(temp->data);
    
    if (temp->left != nullptr) {
      q.push(temp->left);
    }

    if (temp->right != nullptr) {
      q.push(temp->right);
    }
  }
}

void another_display_tree(BinaryTreeNode* root, int tabs) {
  if (root != nullptr) {
    int i;

    if (root->left != nullptr) {
      for(i = 0; i < tabs+4; ++i) {
        cout << ' ';
      }
      cout << "L" << root->left->data << endl;
    }

    if (root->right != nullptr) {
      for(i = 0; i < tabs+4; ++i) {
        cout << ' ';
      }
      cout << "R" << root->right->data << endl;
    }

    another_display_tree(root->left, tabs + 4);
    another_display_tree(root->right, tabs + 4);
  }
}

void another_display_tree(BinaryTreeNode* root) {
  if (root != nullptr) {
    cout << root->data << endl;
    another_display_tree(root, 0);
  }
}

bool is_identical_tree(BinaryTreeNode* root1, BinaryTreeNode* root2) {
  if (root1 == nullptr && root2 == nullptr) {
    return true;
  }
  else if (root1 != nullptr && root2 != nullptr) {
    return ((root1->data == root2->data) &&
            is_identical_tree(root1->left, root2->left) &&
            is_identical_tree(root1->right, root2->right));
  }
  else {
    return false;
  }
}

void populate_parents_rec(BinaryTreeNode* root, BinaryTreeNode* parent) {
  if (root == nullptr) {
    return;
  }

  root->parent = parent;

  populate_parents_rec(root->left, root);
  populate_parents_rec(root->right, root);
}

void populate_parents(BinaryTreeNode* root) {
  populate_parents_rec(root, nullptr);
}

bool are_identical_trees(BinaryTreeNode* root1, BinaryTreeNode* root2) {
  if (root1 == nullptr && root2 == nullptr) {
    return true;
  }
  
  if (root1 != nullptr && root2 != nullptr) {
    return ((root1->data == root2->data) &&
            are_identical_trees(root1->left, root2->left) &&
            are_identical_trees(root1->right, root2->right));
  }

  return false;
}

void print(vector<int>& v) {
  cout << "vector = {";
  for (int x : v) {
    cout << x << ",";
  }
  cout << "}" << endl;
}

template <class T>
void print_list(vector<T>& v) {
  cout << "{ ";
  for (auto x : v) {
    cout << x << ",";
  }
  cout << "}" << endl;
}

template <class T>
bool is_equal(vector<T>& v1, vector<T>& v2) {
  if (v1.size() != v2.size()) {
    return false;
  }

  int idx = 0;
  for (auto x : v1) {
    if (x != v2[idx]) {
      return false;
    }
    ++idx;
  }

  return true;
}

template<typename T>
vector<T> create_random_vector(int length, T max_value = 100) {
  vector<T> v(length);
  srand (time(nullptr));
  for(T i = 0; i < length; ++i) {
    v[i] = static_cast<T>(rand() % max_value);
  }
  return v;
}

vector<int> create_random_vector(int length, int max_value = 100) {
  vector<int> v(length);
  srand (time(nullptr));
  for(int i = 0; i < length; ++i) {
    v[i] = rand() % max_value;
  }
  return v;
}

int find_in_vector(vector<int>& v, int k) {
  for (int i = 0; i < v.size(); ++i) {
    if (k == v[i]) {
      return i;
    }
  }
  return -1;
}

bool is_sorted(vector<int> v) {

  for (int i = 1; i < v.size(); ++i) {
    if (v[i] < v[i-1]) {
      return false;
    }
  }

  return true;
}

void level_order_using_next(BinaryTreeNode* root) {
  while (root != nullptr) {
    cout << root->data << ",";
    root = root->next;
  }
  cout << endl;
}

class mirrorBT{
  public static void mirror_binary_tree(
      BinaryTreeNode root) {
    //TODO: Write - Your - Code
  }
} 

import java.util.*;
import java.math.*;

class BinaryTreeNode
{
    public int data;
    public BinaryTreeNode left;
    public BinaryTreeNode right;

    // below data members used only for some of the problems
    public BinaryTreeNode next;
    public BinaryTreeNode parent;
    public int count;

    public BinaryTreeNode(int d) {
      data = d;
      left = null;
      right = null;
      parent = null;
      count = 0;
    }
}
class BinaryTree {

public static BinaryTreeNode root;

public BinaryTree() {
  root = null;
}

public BinaryTree(BinaryTreeNode head) {
  this.root = head;
}

public static BinaryTreeNode insert(BinaryTreeNode root, int d) {

  BinaryTreeNode pNew = new BinaryTreeNode(d);
  if (root == null) {
    return pNew;
  }

  BinaryTreeNode parent = null;
  BinaryTreeNode pTemp = root;
  while (pTemp != null) {
    parent = pTemp;
    if (d <= pTemp.data) {
      pTemp = pTemp.left;
    } else {
      pTemp = pTemp.right;
    }
  }

  if (d <= parent.data) {
    parent.left = pNew;
    pNew.parent = parent;
  } else {
    parent.right = pNew;
    pNew.parent = parent;
  }  
  return root;
}

public static BinaryTreeNode insert_BT(BinaryTreeNode root, int d) {

  BinaryTreeNode pNew = new BinaryTreeNode(d);
  if (root == null) {
    return pNew;
  }

  BinaryTreeNode parent = null;
  BinaryTreeNode pTemp = root;
  while (pTemp != null) {
    parent = pTemp;
    if (d <= pTemp.data) {
      pTemp = pTemp.left;
    } else {
      pTemp = pTemp.right;
    }
  }

  Random generator = new Random();
  int dir = generator.nextInt(1000);

  if (dir%2 == 0) {
    parent.left = pNew;
    pNew.parent = parent;
  } else {
    parent.right = pNew;
    pNew.parent = parent;
  }  
  return root;
}

public static BinaryTreeNode find_in_bst(BinaryTreeNode root, int d){
  if(root == null)
    return null;

  if(root.data == d) {
    return root;
  }
  else if(root.data > d){
    return find_in_bst(root.left,d);
  }
  else{
    return find_in_bst(root.right,d);
  }
}


public static void display_inorder(BinaryTreeNode node) {
  if (node == null) {
    return;
  }
  display_inorder(node.left);
  if(node.parent != null)
  {
    //System.out.print(String.format("[%d - %d]",node.parent.data, node.count));
  }
  System.out.print(node.data + ", ");
  display_inorder(node.right);
}

public static void get_inorder(BinaryTreeNode node, List<Integer> output) {
  if (node == null) {
    return;
  }
  get_inorder(node.left, output);
  output.add(node.data);
  get_inorder(node.right, output);
}

public static void get_preorder(BinaryTreeNode node, List<Integer> output) {
  if (node == null) {
    return;
  }
  output.add(node.data);
  get_preorder(node.left, output);
  get_preorder(node.right, output);
}

public static BinaryTreeNode create_BST(List<Integer> l) {
  BinaryTreeNode root = null;
  for (Integer x : l) {
    root = insert(root, x);
  }
  return root;
}

public static BinaryTreeNode create_random_BST(int count, int max_value) {
  BinaryTreeNode root = null;
  for (int i = 0; i < count; ++i) {
    Random generator = new Random();
    root = insert(root, generator.nextInt(max_value));
  }
  return root;
}

public static BinaryTreeNode create_random_BST(int count) {
  return create_random_BST(count, Integer.MAX_VALUE);
}

public static BinaryTreeNode create_binary_tree(int count) {
  BinaryTreeNode root = null;
  for (int i = 0; i < count; ++i) {
    Random generator = new Random();
    root = insert_BT(root, generator.nextInt(100));
  }
  return root;
}

private static void populate_parents_rec(BinaryTreeNode root, BinaryTreeNode parent) {
  if (root == null) {
    return;
  }

  root.parent = parent;

  populate_parents_rec(root.left, root);
  populate_parents_rec(root.right, root);
}

public static void populate_parents(BinaryTreeNode root) {
  populate_parents_rec(root, null);
}

public static void bst_to_arraylist_rec(BinaryTreeNode root, ArrayList<Integer> arr) {
  if (root == null) {
    return;
  }

  bst_to_arraylist_rec(root.left, arr);
  arr.add(root.data);
  bst_to_arraylist_rec(root.right, arr);
}

public static ArrayList<Integer> bst_to_arraylist(BinaryTreeNode root) {
  ArrayList<Integer> arr = new ArrayList<Integer>();
  bst_to_arraylist_rec(root, arr);
  return arr;
}

public static void another_display_tree(BinaryTreeNode root, int tabs) {
  if (root != null) {
    int i;

    if (root.left != null) {
      for(i = 0; i < tabs+4; ++i) {
        System.out.print(" ");
      }
      System.out.print("L" + root.left.data + "\n");
    }

    if (root.right != null) {
      for(i = 0; i < tabs+4; ++i) {
        System.out.print(" ");
      }
      System.out.print("R" + root.right.data + "\n");
    }

    another_display_tree(root.left, tabs + 4);
    another_display_tree(root.right, tabs + 4);
  }
}

public static void another_display_tree(BinaryTreeNode root) {
  if (root != null) {
    System.out.print(root.data + "\n");
    another_display_tree(root, 0);
  }
}

public static void display_level_order(BinaryTreeNode root) {
  if(root == null)
    return;

  ArrayDeque<BinaryTreeNode> queue = new ArrayDeque<BinaryTreeNode>();
  queue.addLast(root);

  while(!queue.isEmpty()){
    BinaryTreeNode temp = queue.removeFirst();
    System.out.print(temp.data + ", ");

    if(temp.left != null) {
      queue.addLast(temp.left);
      //System.out.println(temp.left.data + "LEFT");
    }

    if(temp.right != null){
      queue.addLast(temp.right);
      //System.out.println(temp.right.data + "RIGHT");
    }
  }
    System.out.println();
}

public static List<Integer> get_level_order(BinaryTreeNode root) {

  List<Integer> output = new ArrayList<Integer>();

  if(root == null)
    return output;

  ArrayDeque<BinaryTreeNode> queue = new ArrayDeque<BinaryTreeNode>();
  queue.addLast(root);

  while(!queue.isEmpty()){
    BinaryTreeNode temp = queue.removeFirst();
    // System.out.print(temp.data + ", ");
    output.add(temp.data);

    if(temp.left != null) {
      queue.addLast(temp.left);
      //System.out.println(temp.left.data + "LEFT");
    }

    if(temp.right != null){
      queue.addLast(temp.right);
      //System.out.println(temp.right.data + "RIGHT");
    }
  }
  return output;
}

public static boolean is_identical_tree(BinaryTreeNode root1, BinaryTreeNode root2) {
  if (root1 == null && root2 == null) {
    return true;
  }
  else if (root1 != null && root2 != null) {
    return ((root1.data == root2.data) &&
            is_identical_tree(root1.left, root2.left) &&
            is_identical_tree(root1.right, root2.right));
  }
  else {
    return false;
  }
}
}

class ListUtil{
  public static <T> boolean is_equal(List<T> v1, List<T> v2) {
    if(v1.size() != v2.size()){
      return false;
    }

    for(int i= 0 ; i < v1.size() ; i++) {
      if(!v1.get(i).equals(v2.get(i))) {
        System.out.println(v1.get(i) + "not equal" + v2.get(i));
        return false;
      }
    }

    return true;
  }

  /*public static boolean is_equal(List<Integer> v1, List<Integer> v2) {
    if(v1.size() != v2.size()){
      return false;
    }
    for(int i= 0 ; i < v1.size() && i < v2.size(); i++) {
      //System.out.print(String.format("\n%d-%d\n", v1.get(i),v1.get(i)));
      if(v1.get(i) - v2.get(i) != 0) {
        return false;
      }
    }
    System.out.print(String.format("\nTRUE\n"));
    return true;
  }*/

  public static void print(List<Integer> l) {
    for (Integer i : l) {
      System.out.print(i + ", ");
    }
    System.out.println();
  }

  public static ArrayList<Integer> createRandomList(int length) {
    ArrayList<Integer> l = new ArrayList<Integer>();
    for (int i = 1; i < length + 1; ++i) {
      l.add(i);
    }

    Collections.shuffle(l);
    return l;
  }

  public static List<Integer> create_random_list(int length, int max_value) {
    List<Integer> l = new ArrayList<Integer>();
    for (int i = 1; i < length + 1; ++i) {
      l.add(new Random().nextInt(max_value));
    }

    Collections.shuffle(l);
    return l;
  }
}

Java

def mirror_tree(root):
  #TODO: Write - Your - Code
  return root

import os, sys, io, pickle
utils_path = os.path.join('..', '..', '..', '..', 'problems', 'utils', 'python')
sys.path.append(utils_path)
from copy import *
from collections import deque

def print_list(v):
  for i in range(0,len(v)):
    print(str(v[i]), end = " ")
  print("")

def are_lists_equal(v1, v2):
  if len(v1) != len(v2):
    return False

  for n1, n2 in zip(v1, v2):
    if n1 != n2:
      return False

  return True

def create_random_list(count):
  output = []
  for i in range(0, count):
    output.append(random.randrange(1, sys.maxint))
  return output


class BinaryTreeNode:
  def __init__(self, data):
    self.data = data
    self.left = None
    self.right = None
    self.next = None
    self.parent = None


import random

def level_order_traversal(root):
  result = ""
  if root == None:
    return
  q = deque()
  q.append(root)
  while q:
    temp = q.popleft()
    result += str(temp.data) + " "
    if temp.left != None:
      q.append(temp.left)
    if temp.right != None:
      q.append(temp.right)
  return result    
      

def insert_binary_tree(root, d):
  pNew = BinaryTreeNode(d)
  if root == None:
    return pNew

  parent = None
  pTemp = root
  while (pTemp != None): 
    parent = pTemp
    if d < pTemp.data:
      pTemp = pTemp.left
    else:
      pTemp = pTemp.right

  if d <= parent.data:
    parent.right = pNew
  else:
    parent.left = pNew

  return root

def insert(root, d):
  pNew = BinaryTreeNode(d)
  if root == None:
    return pNew

  parent = None
  pTemp = root
  while (pTemp != None): 
    parent = pTemp
    if d < pTemp.data:
      pTemp = pTemp.left
    else:
      pTemp = pTemp.right

  if d < parent.data:
    parent.left = pNew
  else:
    parent.right = pNew

  return root

def find_in_bst(root, d):
  if root == None:
    return None

  if root.data == d:
    return root
  elif root.data > d:
    return find_in_bst(root.left, d)
  else:
    return find_in_bst(root.right, d)

# find node in inorder 
# works for both BST and binary tree
def find_node(root, d):
  if root == None:
    return

  if root.data == d:
    return root

  temp = find_node(root.left, d)
  if temp != None:
    return temp

  return find_node(root.right, d) 

def display_inorder(node):
  if node == None:
    return

  display_inorder(node.left)
  print(str(node.data), end = " ") 
  display_inorder(node.right)

def create_BST(arr):
  root = None
  for x in arr:
    root = insert(root, x)
  return root

def create_binary_tree(count):
  root = None
  for i in range(1, count):
    root = insert_binary_tree(root, random.randrange(1,100))
  return root

def create_random_BST(count):
  root = None;
  for i in range(1, count):
    root = insert(root, random.randrange(200, 300))
  return root

def bst_to_list_rec(root, lst):
  if root == None:
    return

  bst_to_list_rec(root.left, lst)
  lst.append(root.data)
  bst_to_list_rec(root.right, lst)

def bst_to_list(root):
  lst = []
  bst_to_list_rec(root, lst)
  return lst

def insert_at_head(head, data):
  newNode = LinkedListNode(data)
  newNode.next = head
  return newNode

def populate_parents_rec(root, parent):
  if root == None:
    return 
  root.parent = parent

  populate_parents_rec(root.left, root)
  populate_parents_rec(root.right, root)

def populate_parents(root):
  populate_parents_rec(root, None)

def display_level_order(root):
  if root == None:
    return
  q = deque()
  q.append(root)

  while q:
    temp = q.popleft()
    print(str(temp.data), end = ",")
    if temp.left != None:
      q.append(temp.left)
    if temp.right != None:
      q.append(temp.right)

  print

def get_level_order(root):
  output = []
  if root == None:
    return output
  
  q = deque()
  q.append(root)

  while q:
    temp = q.popleft()
    output.append(temp.data)
    if temp.left != None:
      q.append(temp.left)
    if temp.right != None:
      q.append(temp.right)

  return output

def get_inorder_helper(root, output):
  if root == None:
    return output

  output = get_inorder_helper(root.left, output)
  output.append(root.data)
  output = get_inorder_helper(root.right, output)
  
  return output

def get_inorder(root):
  output = []
  return get_inorder_helper(root, output)

def is_identical_tree(root1,root2):
  if root1 == None and root2 == None:
    return True

  if root1 != None and root2 != None and root1.data == root2.data: 
    return is_identical_tree(root1.left,root2.left) and is_identical_tree(root1.right,root2.right)

  return False

Python

let mirror_tree = function(root) {
  //TODO: Write - Your - Code
  return root;
};

JavaScript

def mirror_tree(root)
  #TODO: Write - Your - Code
  return root
end

class BinaryTreeNode
  attr_accessor :data, :left, :right, :next, :parent, :count
  def initialize(data)
    @data = data
    @left = nil
    @right = nil
    @next = nil
    @parent = nil
    @count = -1
  end
end

def insert_binary_tree(root, d)
  pNew = BinaryTreeNode.new(d)
  if (!root)
    return pNew
  end

  parent = nil
  pTemp = root
  while (pTemp)
    parent = pTemp
    if (d < pTemp.data)
      pTemp = pTemp.left
    else
      pTemp = pTemp.right
    end
  end
  if (d <= parent.data)
    parent.right = pNew
  else
    parent.left = pNew
  end

  return root
end

def insert(root, d)
  pNew = BinaryTreeNode.new(d)
  if (!root)
    return pNew
  end

  parent = nil
  pTemp = root
  while (pTemp)
    parent = pTemp
    if (d < pTemp.data)
      pTemp = pTemp.left
    else
      pTemp = pTemp.right
    end
  end
  if (d < parent.data)
    parent.left = pNew
  else
    parent.right = pNew
  end

  return root
end

def find_in_bst(root, d)
  if (!root)
    return nil
  end

  if (root.data == d)
    return root
  elsif (root.data > d)
    return find_in_bst(root.left, d)
  else
    return find_in_bst(root.right, d)
  end
end

# find node in inorder
# works for both BST and binary tree
def find_node(root, d)
  if (!root)
    return
  end

  if (root.data == d)
    return root
  end

  temp = find_node(root.left, d)
  if (temp)
    return temp
  end

  return find_node(root.right, d)
end

def display_inorder(node)
  if (!node)
    return
  end

  display_inorder(node.left)
  print (node.data.to_s + ", ")
  display_inorder(node.right)
end
def create_BST(arr)
  root = nil
  arr.each do |x|
    root = insert(root, x)
  end
  return root
end

def create_binary_tree(count)
  root = nil
  (count-1).times do |i|
    root = insert_binary_tree(root, (rand * 100 + 1).floor)
  end
  return root
end

def create_random_BST(count)
  root = nil
  (count-1).times do |i|
    root = insert(root, (rand * 100 + 200).floor)
  end
  return root
end

def bst_to_list_rec(root, lst)
  if (!root)
    return
  end

  bst_to_list_rec(root.left, lst)
  lst.push(root.data)
  bst_to_list_rec(root.right, lst)
end

def bst_to_list(root)
  lst = []
  bst_to_list_rec(root, lst)
  return lst
end

def populate_parents_rec(root, parent)
  if (!root)
    return
  end
  root.parent = parent

  populate_parents_rec(root.left, root)
  populate_parents_rec(root.right, root)
end

def populate_parents(root)
  populate_parents_rec(root, nil)
end

def display_level_order(root)
  if (!root)
    return
  end
  q = []
  q.push(root)
  print_level = ''
  while (q.length > 0)
    temp = q.shift()
    print_level += temp.data.to_s + ","
    if (temp.left)
      q.push(temp.left)
    end
    if (temp.right)
      q.push(temp.right)
    end
  end
  print (print_level)
end

def level_order_traversal(root)
  if (!root)
    return
  end
  q = []
  res = ""
  q.push(root)
  print_level = ''
  while (q.length > 0)
    temp = q.shift()
    print_level += temp.data.to_s + " "
    if (temp.left)
      q.push(temp.left)
    end
    if (temp.right)
      q.push(temp.right)
    end
  end
  return print_level
end


def get_level_order(root)
  output = []
  if (!root)
    return output
  end

  q = []
  q.push(root)

  while (q.length > 0)
    temp = q.shift()
    output.push(temp.data)
    if (temp.left)
      q.push(temp.left)
    end
    if (temp.right)
      q.push(temp.right)
    end
  end
  return output
end

def get_inorder_helper(root, output)
  if (!root)
    return output
  end

  output = get_inorder_helper(root.left, output)
  output.push(root.data)
  output = get_inorder_helper(root.right, output)

  return output
end

def get_inorder(root)
  output = []
  return get_inorder_helper(root, output)
end

def is_identical_tree(root1, root2)
  if (!root1 && !root2)
    return true
  end

  if (root1 && root2 && root1.data == root2.data)
    return is_identical_tree(root1.left, root2.left) && is_identical_tree(root1.right, root2.right)
  end

  return false
end

Ruby

void mirror_tree(BinaryTreeNode* root) {
  if (root == nullptr) {
    return;
  }

  // We will do a post-order traversal of the binary tree.

  if (root->left != nullptr) {
    mirror_tree(root->left);
  }

  if (root->right != nullptr) {
    mirror_tree(root->right);
  }

  // Let's swap the left and right nodes at current level.

  BinaryTreeNode* temp = root->left;
  root->left = root->right;
  root->right = temp;
}

int main(int argc, char* argv[]) {

  BinaryTreeNode* root = create_random_BST(15);
  display_level_order(root);
  mirror_tree(root);
  cout << endl << "Mirrored tree = " << endl;
  display_level_order(root);
}

class mirrorBT{
  public static void mirror_binary_tree(
      BinaryTreeNode root) {
  
    if (root == null) {
      return;
    }

    // We will do a post-order traversal of the binary tree.

    if (root.left != null) {
      mirror_binary_tree(root.left);
    }

    if (root.right != null) {
      mirror_binary_tree(root.right);
    }

    // Let's swap the left and right nodes at current level.

    BinaryTreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
  }
  public static void main(String[] argv) {
    BinaryTreeNode root = BinaryTree.create_random_BST(15,100);
    BinaryTree.display_level_order(root);
    System.out.println();

    mirror_binary_tree(root);

    BinaryTree.display_level_order(root);  
  }
}  

def mirror_tree(root):
  if root == None:
    return

  # We will do a post-order traversal of the binary tree.
  if root.left != None:
    mirror_tree(root.left)

  if root.right != None:
    mirror_tree(root.right)

  # Let's swap the left and right nodes at current level.
  temp = root.left
  root.left = root.right
  root.right = temp
  

def level_order_traversal(root):
  if root == None:
    return
  q = deque()
  q.append(root)

  while q:
    temp = q.popleft()
    print(str(temp.data), end = ",")
    if temp.left != None:
      q.append(temp.left)
    if temp.right != None:
      q.append(temp.right)

arr = [100,25,75,15,350,300,10,50,200,400,325,375]
root = create_BST(arr)
#root = create_random_BST(15)
print("\nLevel Order Traversal:", end = "")
level_order_traversal(root)

mirror_tree(root)
print("\nMirrored Level Order Traversal:", end = "")
level_order_traversal(root)

def mirror_tree(root)
  if (!root)
    return
  end

  # We will do a post-order traversal of the binary tree.
  if (root.left)
    mirror_tree(root.left)
  end

  if (root.right)
    mirror_tree(root.right)
  end

  # Let's swap the left and right nodes at current level.
  temp = root.left
  root.left = root.right
  root.right = temp
end

def main()
  root = create_random_BST(15)
  print "\nLevel Order Traversal: "
  display_level_order(root)
  mirror_tree(root)
  print "\nMirrored Level Order Traversal: "
  display_level_order(root)
  puts
end

main

# Solution Explanation
## Runtime Complexity
Linear, O(n).

Every sub-tree needs to be mirrored so we visit every node once and mirror the sub-tree starting there. Hence run time complexity is O(n).

## Memory Complexity
Linear, O(n) in the worst case.

<br>

## Solution Breakdown

Recursive solution has O(h) memory complexity, for a balanced tree, as it will consume memory on the stack up to the height of the binary tree. For a skewed tree, it can be O(n).

Here, we will do a post order traversal of the binary tree. For every node, we will swap it's left child with its right child. The original nodes are shown in green color while the nodes that have been swapped are shown in grey. The node at the top of the stack (current node) is shown in light blue. Note that we are doing DFS on the tree i.e. before returning from a node all its children have been visited (and mirrored).

> Practice problems like this and many more by checking out our [Grokking the Coding Interview: Patterns for Coding Questions](https://www.educative.io/courses/grokking-the-coding-interview) course!

Given the root node of a binary tree, swap the 'left' and 'right' children for each node.

Mirror Binary Tree Nodes

Problem Statement

Hint

Try it yourself

Solution

Solution Explanation

Runtime Complexity

Memory Complexity

Solution Breakdown