Given a node in binary tree - Check if left and right subtree are mirror of each other

Problem

A binary tree is a mirror image of itself if its left and right subtrees are identical mirror images i.e., the binary tree is symmetrical. This is best explained with a few examples.

Example

  1
 / \
2   2

TRUE

   1
  / \
 2   2
  \
   3

FALSE

     1
   /   \
  2     2
 / \   / \
4   3 3   4

TRUE

       1
     /   \
    2     2 
   / \   / \
  3   4 3   4

FALSE

       1
     /   \
    2     2
   /       \
  3         3

TRUE

Solution

Method 1 - Recursiion mirrorEquals(BTree left , BTree right)
Basically compare the left subtree and inverted right subtree, drawing an imaginary line of inversion across root.

boolean mirrorEquals(BTree left, BTree right) {
  if (left == null || right == null) return left == null && right == null;
  return left.value == right.value 
         && mirrorEquals(left.left, right.right) 
   && mirrorEquals(left.right, right.left);
}

Method 2 - Iterative solution using queue
Insert 2 elements at a time and then pop and compare the values, and continue to do with the children.

bool isMirrorItselfIteratively(BTree root) 
{
    /// use single queue and initial push
    if(!root) return true;
    queue<btree> q;
    q.push(root.left);
    q.push(root.right);
 
    BTree l, r;
    while(!q.empty()) {
        l = q.front();
        q.pop();
        r = q.front();
        q.pop();
        if(l==NULL && r==NULL) continue;
        if(l==NULL || r==NULL ) return false;
  if(l.data!=r.data) return false;
  //not the push ordering
        q.push(l.left);
        q.push(r.right);
        q.push(l.right);
        q.push(r.left);
    }

    return true;
}

References 

• http://stackoverflow.com/questions/8436623/check-if-a-binary-tree-is-a-mirror-image-or-symmetric

Read More

Queue ADT

Definition :-
A queue is a collection of same type of entities, which ensures that all entities in collection will have a sequential storage structure that permits access only at the two ends of the sequence.  We refer to the ends of the sequence as the front and rear.  The first element in queue have the position as front and value or pointer or front changes according to the solution of the given problem. Rear is the terminal position of the queue, this can be the position of the last element or last point of the queue. A queue inserts new elements at the rear and removes elements from the front of the sequence, to maintain the sequential storage structure.  You will note that a queue removes elements in the same order in which they were stored, and hence a queue provides FIFO (first-in / first-out), or FCFS (first-come, first-served), ordering.


Example :-  Consider that you and your family went zoo. First you have to buy a ticket, so you or one of member of your group have to join the line for ticket counter. every person in that line will get the ticket in same sequence, in which they join that line. So this is one of the common example of queue.

 

Advanced Data Structure of Queue:- 

Advanced data structure involve the following steps:

• how to define a data structure type,
• create a data structure to implement the function performed by or associated to the new type
• implement the above two in any programming language.

There are many operations which we can perform with a queue to solve any problem. Basic operations or function of queue are as follows:

• queue() creates a new queue that is empty. It needs no parameters and returns an empty queue.
• enqueue(item) adds a new item to the rear of the queue. It needs the item and returns nothing.
• dequeue() removes the front item from the queue. It needs no parameters and returns the item. The queue is modified.
• isEmpty() tests to see whether the queue is empty. It needs no parameters and returns a boolean value.
• size() returns the number of items in the queue. It needs no parameters and returns an integer.

Read More