Binary Tree Inversion

 This is a special article to show you how to invert a binary tree. A binary tree is a data structure where data types (integers, floats, strings) are stored in a tree. This tree as the name suggests has two children: Left child and Right child and a root node at the top of the tree. Normally, left child is stored at the left side of a node and the right child at the right side of the node.

Look at the image: 

Google image

To design an algorithm for a binary tree is easy. I am going to focus on how to get its mirror image once you have created a binary tree.

Algorithm to create mirror image of binary tree

Once you have created a binary tree, you get a root node of this tree.

What is the difference(s) between normal binary tree and its mirror image?

Ans: In a binary tree, for a parent node, its children have swapped their positions, i.e , left child became right child and vice-versa to become inverted binary tree. Root node stays at the same position.

Algorithm:

Step1. Start traversing the tree until you get the null node

           (Either start from left child or right child)

Step2. Once you get null node, return and swap your left and right child.

              And Voila, It's done!!!

Code:

---

Stack and Queue implementation in C++

Stack (also known as LIFO) and Queue(also known as FIFO) are two abstract data types in computer science that serve as collection of elements.

There are some specific operations associated with these two data types:

1. Push
2. Pop

Third operation is basically 'look up' (to see the top element in stack/queue).

All these three operations should take O(1) to process.

To know details of stack and queue, you can look up wikipedia[1][2]  to know more.

I am here to show you the implementation of these two in C++.

I am using linked list to implement it. Linked list has usual properties : node, head and link

---

Stack:

using namespace std;
class Stack{
public:
Stack* next;   // link between two nodes
Stack* head=NULL; // to gateway to enter the linked list (in this case our stack)
int data;
void push(int data){
Stack* s=new Stack();    // create a new node
s->data=data;
s->next=head;
head=s;
}
void pop(){
head=head->next;
}
int top(){
return head->data;
}
};

int main(){
Stack* s=new Stack();
s->push(12);
s->push(19);
s->push(23);
s->push(34);
s->pop();
cout << s->top() << endl;
return 0;
}

---

Queue:

#include <iostream>
using namespace std;
class Queue{
public:
Queue* next;
Queue* head=NULL;
Queue* tail=NULL;  // so that new element can be added to the queue in O(1) time.
int data;
void push(int data){
Queue* q=new Queue();
q->data=data;
q->next=NULL;
if(head==NULL){
head=q;
tail=q;
}else{
tail->next=q;
tail=q;
}
}
void pop(){
head=head->next;
}
int top(){
return head->data;
}
};

int main(){
Queue* q=new Queue();
q->push(12);
q->push(19);
q->push(23);
q->push(34);
q->pop();
q->pop();
cout << q->top() << endl;
return 0;
}

If I missed something, please let me know.
Happy coding !

---

Terms used in the blog:

LIFO: Last in first out

FIFO: First in first out

Reference:
Stack
Queue
Abstract data types