Clone a Binary Tree with Random Pointers

Given a Binary Tree where every node has following structure.

struct node {  
    int key; 
    struct node *left,*right,*random;
} 

The random pointer points to any random node of the binary tree and can even point to NULL, clone the given binary tree.

http://www.geeksforgeeks.org/clone-binary-tree-random-pointers/

Binary Tree in cartesian plane

Assume that a binary tree is drawn over a Cartesian coordinate system (with X & Y axis) where the leftmost node is placed at point (0,0). So, we need to traverse the nodes and print in following manner:
For e.g., for this tree
a
b c
d e f g

Output should be:
d,0,0
b,1,1
e,2,0
a,3,2
f,4,0
c,5,1
g,6,0

Strategy:

You can easily note here that for any given node:
the x-coordinate is its cardinal (order) in an inorder traversal; and
the y coordinate is the number of levels in the tree rooted at that node;
Using these 2 pieces you can easily get the output shown above...

int print(node* n, int &count) {
    if (!n) return -1;
    int height = print(n->left, count) + 1;
    printf("%d,%d,%d", n->data, count++, height);
    print(n->right, count);
    return height;
}
print(root, 0);

Binary Tree Traversal-Modified

WAP to print the node values of a binary tree
- Even level starting from right to left
- Odd level starting from left to right
Assume that level of root is 1.
a
b c
d e f g
Output: a c b d e f g

Strategy:

Method 1:Two Stacks

static void print(Node root)
{
Stack<Node> odd = new Stack<Node>();
Stack<Node> even = new Stack<Node>();
odd.Push(root);
while (odd.Count != 0 || even.Count != 0)
{
while (odd.Count != 0)
{
Node node = odd.Pop();
if(node.left!=null)
even.Push(node.left);
if(node.right!=null)
even.Push(node.right);
Console.Write(node.data+" ");
}
Console.WriteLine();
while (even.Count != 0)
{
Node node = even.Pop();
if (node.right != null)
odd.Push(node.right);
if (node.left != null)
odd.Push(node.left);
Console.Write(node.data + " ");
}
Console.WriteLine();
}
}

Method 2:

 Breadth First Search with a stack can solve this problem.
1. Add the root node to the queue.
2. Get the head node of the queue and add its children to the queue.
3. If the node is in even level, print it. Otherwise, push it into the stack
4. When level of the head node has changed from odd to even,pop the stack and print the node
5. Repeat from 2 until all the node have been scaned

Nodes at same depth

Problem is to find print all the nodes at the same levels of a binary tree.Inputs given are root pointer and the pointer to the node (let it be A)whose level elements need to be printed.


Strategy:
Find the depth of the node A.
Then do a depth wise traversal of the tree by tracking the level u are at currently.
Now when u get a node of equal depth as A then print it and do a back traversal from there as other nodes from the current node will result in a higher depth. Thus we can find all the nodes at the current level.

Print Ancestors of a node in a Binary Tree:

Print Ancestors of a node in a Binary Tree


Strategy:


#include <stdio.h>
#include <stdlib.h>

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

int isAncestor(struct node* root, int n)
{
    if(root == NULL)
        return 0;

    if(root->data == n)
        return 1;

    if(isAncestor(root->left, n) || isAncestor(root->right, n))
    {
        printf("%d\n", root->data);
        return 1;
    }
    return 0;
}

struct node* newnode(int data)
{
  struct node* node = (struct node*)
                       malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;
//  node->nextRight = NULL;

  return(node);
}

int main()
{

    /* Constructed binary tree is
              10
            /   \
          8      2
        /         \
      3            90
       \
        14
    */
    struct node *root = newnode(10);
    root->left        = newnode(8);
    root->right       = newnode(2);
    root->left->left  = newnode(3);
    root->right->right       = newnode(90);
    root->right->right->left       = newnode(14);

    isAncestor(root, 14);
    getchar();
    return 0;
}

Time Complexity: O(n) where n is the number of nodes in the given Binary Tree

Nearest sibling of a node

Find the nearest sibling of a given node in a tree. Nodes on same level are siblings of each other.
_________A_________
_____B________C____
___D___E____H_____
__F_____G__I_______
Nearest sibling of G is I

Strategy:

Do breadth first traversal of a tree ..
For this, we need one FIFO queue . Starting from root of the tree, go on queuing nodes in a queue at each level, then dequeue the front node and enqueue it's children and so on ...
In above example,
1. Enqueue A - Queue = A
2. Dequeue A and Enqueue B and C - Queue = B C
3. Dequeue B and Enqueue D and E - Queue = C D E
4 .Dequeue C and Enqueue H - Queue = D E H
5. Dequeue D and Enqueue F - Queue = E H F
6. Dequeue E and Enqueue G - Queue = H F G
7. Dequeue H and Enqueue I - Queue = F G I
8. Dequeue F - Queue = G I
Hence, in the queue we can see that nearest sibling of G is I.

Build the tree from ancestor matrix

A tree is represented as a matrix where a(i,j) = 1 if j is ancestor of i. Build the tree.

Longest zigzag path in a binary tree

Find the longest zigzag path in binary tree.

Code:

int maxZigzag(struct node* root)
{
    int lcount = 0;
    int rcount = 0;
    int max = 0;
    struct node* temp = root;

    if(root == NULL)
        return 0;

    while(1)
    {
        if(temp->left != NULL)
        {
            lcount++;
            temp = temp->left;
        }
        else
            break;

        if(temp->right != NULL)
        {
            lcount++;
            temp = temp->right;
        }
        else
            break;
    }
    
    while(1)
    {
        if(temp->right != NULL)
        {
            rcount++;
            temp = temp->right;
        }
        else
            break;

        if(temp->left != NULL)
        {
            rcount++;
            temp = temp->left;
        }
        else
            break;
    }

    max = MAX(lcount, rcount);
    max = MAX(max, maxZigzag(root->left));
    max = MAX(max, maxZigzag(root->right));

    return max;
}

int main()
{
    struct node *root;

    insert(&root, 100);
    insert(&root, 50);
    insert(&root, 25);
    insert(&root, 40);
    insert(&root, 30);
    insert(&root, 35);
    insert(&root, 120);
    insert(&root, 110);
    insert(&root, 32);

    printf("maxZigzag = %d\n", maxZigzag(root));
    return 0;
}

Vertical Columns / Vertical sum in a Binary tree

Question 1:Count the number of vertical columns in a tree
Question 2:Find vertical sum of given binary tree.
Example:

1
    / \
  2     3
 / \   / \
4   5 6   7

The tree has 5 vertical lines

Vertical-1: nodes-4     => vertical sum is 4       
Vertical-2: nodes-2     => vertical sum is 2
Vertical-3: nodes-1,5,6 => vertical sum is 1+5+6 = 12
Vertical-4: nodes-3     => vertical sum is 3
Vertical-5: nodes-7     => vertical sum is 7

We need to output: 4 2 12 3 7
http://www.geeksforgeeks.org/vertical-sum-in-a-given-binary-tree/

Question 3:Print elements that are in a vertical column (per column) in a Binary tree

Total Number of Columns:

Every node in a binary tree can be considered belonging to a column. If we assume that 'root' belongs to column '0' then root->left belongs to column '-1', root->right belongs to column '+1' and root->left->right belongs to column '0' and so on. We have to find the total number of such columns.

Code:
#include <stdio.h>
#include <stdlib.h>
#define MAX(a,b) ((a>b)?(a):(b))
#define MIN(a,b) ((a<b)?(a):(b))
struct node
{
    int data;
    struct node *left;
    struct node *right;
};

//typedef tree node;

void insert(struct node *& root,int item){
     if(root==NULL){
          struct node *r= (struct node*)malloc(sizeof(struct node));
          r->data=item;
          r->left=NULL;
          r->right=NULL;
          root=r;
          return;
     }
     if (item< root->data){
        insert(root->left,item);
        return;
     }
     else{
        insert(root->right,item);
        return;
     }
     return;
}

void totalCol(struct node* root, int col, int* minC, int* maxC)
{
    if(root == NULL)
        return;

    totalCol(root->left, col-1, minC, maxC);
    totalCol(root->right, col+1, minC, maxC);

    *minC = MIN(*minC, col);
    *maxC = MAX(*maxC, col);
}

int main()
{
    struct node *root=NULL;

    int minC=0;
    int maxC=0;

    insert(root, 50);
    insert(root, 25);
    insert(root, 100);
    insert(root, 30);
    insert(root, 10);
    insert(root, 5);

    totalCol(root, 0, &minC, &maxC);

    printf("Total Col: %d\n", maxC - minC + 1);

    return 0;
}

Vertical Sum:

Code:

#include <stdio.h>
#include <stdlib.h>

#define MAX_WIDTH 100


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

int height(struct node* node)
{
   if (node==NULL)
       return 0;
   else
   {     
     int lheight = height(node->left);
     int rheight = height(node->right);
    
     if (lheight > rheight)
         return(lheight+1);
     else return(rheight+1);
   }
}

void compute_vertical_sum(struct node *node, int index,int vertical_sum[])
{
if( node == NULL ) return;
vertical_sum[index] += node->data;
compute_vertical_sum( node->left, index-1,vertical_sum);
compute_vertical_sum( node->right, index+1,vertical_sum);
}

struct node* newNode(int data)
{
  struct node* node = (struct node*)
                       malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;

  return(node);
}


int main()
{
  int vertical_sum[MAX_WIDTH]= {0};
  struct node *root = newNode(1);
  root->left        = newNode(2);
  root->right       = newNode(3);
  root->left->left  = newNode(4);
  root->left->right = newNode(5);
  root->left->right->left = newNode(6);
  root->left->left->left  = newNode(9);
  int h=height(root);
  int max_width_possible=2*h+1;

  compute_vertical_sum(root, h,vertical_sum);
 
  for(int i=0; i <max_width_possible; i++)
     if ( vertical_sum[i] > 0 )
          printf("%d  ",vertical_sum[i]);

  getchar();
  return 0;
}


y lies in the path between x and z or not in a Binary Tree

Given a binary tree, and 3 nodes x,y,z write a function which returns true if y lies in the path between x and z and false otherwise.

Code:

int find_y_in_xz_path(Tree t, Node *y, Node *z, int yfound)
{
    if(!t)
        return 0;

    if(t == z)
    {
        return yfound;
    }
    else if(t == y)
    {
        yfound = 1;
    }

    if(find_y_in_xz_path(t->left, y, z, yfound))
        return 1;

    return find_y_in_xz_path(t->right, y, z, yfound);

}

int main()
{
    find_y_in_xz_path(x,y,z,0);
}

Binary Tree Properties

Types:
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.The number of nodes n in a complete binary tree is at least n = 2h and at most  where is the depth of the tree.

A balanced binary tree is commonly defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1

A perfect binary tree is a full binary tree in which all leaves are at the same depth or same level, and in which every parent has two children.The number of nodes n in a perfect binary tree can be found using this formula: n = 2h + 1 - 1 where h is the depth of the tree.The number of leaf nodes L in a perfect binary tree can be found using this formula: L = 2h where h is the depth of the tree.

A rooted binary tree is a tree with a root node in which every node has at most two children.

Size and Depth:
The depth of a node n is the length of the path from the root to the node. The set of all nodes at a given depth is sometimes called a level of the tree. The root node is at depth zero.

The depth of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a depth of zero.

The size of a node is the number of descendants it has including itself.

Questions:
1.A full N ary tree has M non leaf nodes.How many leaf nodes it has ?
M+(N^(n-1))=(1-(N^n))/(1-N)
Here N^(n-1) is the number of leaf nodes.Solving for this leads to
Number of leaf nodes=M*(N-1)+1

2.Using n nodes how many different trees can be constructed?
2^n-n

Populate Grand Parents in Binary Tree

You are given a special kind of binary tree, in which there is another attribute, “grandparent”, which is a pointer to the grandparent of a node. The tree structure is thus,
struct Node
{
int val;
node * left;
node * right;
node * grandparent;
};

1
/ \
2 3
/ \  \
4 5 8

In the tree given to you, the grandparent attribute for each node is initialized to NULL. Write a function to initialize the grandparent attribute.
Note: The value of the “grandparent” attribute for the root and first level nodes will be NULL.

Code:
 #include <stdio.h>
#include <stdlib.h>
#include <limits.h>

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

};


int isLeaf(struct Node *n)
{
return (n->left==NULL && n->right==NULL);

}

int isAtHeightLEOne(struct Node *n)
{

return ((n==NULL) || ((n->left==NULL) ||isLeaf(n->left)) && ((n->right==NULL) || isLeaf(n->right)) );

}

void setGrand(struct Node *p, struct Node *root)
{
if(p->left)
p->left->grandparent=root;

if(p->right)
p->right->grandparent=root;

}

void SetGrandParent(struct Node *t)
{
if(isAtHeightLEOne(t))
return;

struct Node *p=t->left;

if(p)
{
setGrand(p,t);
SetGrandParent(p);

}
p=t->right;
if(p)
{

setGrand(p,t);
SetGrandParent(p);

}

}

struct Node* newNode(int data)
{
struct Node* node = (struct Node*)
malloc(sizeof(struct Node));
node->data = data;
node->left = NULL;
node->right = NULL;
node->grandparent=NULL;

return(node);
}

int main()
{

struct Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(8);

SetGrandParent(root);

printf(" %d %d %d ",root->left->left->grandparent->data,root->left->right->grandparent->data,root->right->left->grandparent->data);

getchar();
return 0;
}

Density of a Binary Tree

Find the density of the given binary tree

Sequences of the leaf elements of two binary trees are same or not

Given references to roots of two binary trees, how do you short circuit determine whether the sequences of the leaf elements of both the trees are same ? The structure of two BTs may be different. Short circuit : for ex. If the very first leaf element of each tree is different, the algorithm should stop immediately returning false instead of checking all the leaf elements of both trees.

                                           5
                               /                       \
                         2                               7
                                       5
                                          \
                                           3
                                      /           \
                                    2             7
for both the above this should return true
but with below one it is false
                                          5
                                        /       \
                                       3        7

Count Number of Trees

Given n number of independent nodes how many trees with different structure can be formed ?

Connect Nodes at same level /Populate next right

Write a function to connect all the adjacent nodes at the same level in a binary tree.
OR
Populate nextRight pointer with next sibling of each node in a binary tree

 Structure of the given Binary Tree node is like following.

struct node{   int data;   struct node* left;   struct node* right;   struct node* nextRight; }

Initially, all the nextRight pointers point to garbage values. Your function should set these pointers to point next right for each node.
Example

Input Tree
       A
      / \
     B   C
    / \   \
   D   E   F

Output Tree
       A--->NULL
      / \
     B-->C-->NULL
    / \   \
   D-->E-->F-->NULL

Solution for Complete BTs

Method 1:Naive Recursion[Only for Complete Binary Tree]

1.The first key to solving this problem is we have the nextRight pointer. Assume that the nextRight pointers are already populated for this level. How can we populate the next level? Easy… just populate by iterating all nodes on this level.
2.Another key to this problem is you have to populate the next level before you go down to the next level, because once you go down, you have no parent pointer, and you would have hard time populating

Method 2 :Modified Pre order Traversal[Works only for complete BT]

In this method we set nextRight in Pre Order fashion to make sure that the nextRight of parent is set before its children. When we are at node p, we set the nextRight of its left and right children. Since the tree is complete tree, nextRight of p’s left child (p->left->nextRight) will always be p’s right child, and nextRight of p’s right child (p->right->nextRight) will always be left child of p’s nextRight (if p is not the rightmost node at its level). If p is the rightmost node, then nextRight of p’s right child will be NULL.

Note:The above two methods only works for complete BTs.WHY

Consider the tree given below

____________1
          /    \
        2        3
       / \      /  \
      4   5    6    7
     / \           / \
    8   9        10   11

In Method 2, we set the nextRight pointer in pre order fashion.  When we are at node 4, we set the 

nextRight of its children which are 8 and 9(the nextRight of 4 is already set as node 5). nextRight of 8 

will simply be set as 9, but nextRight of 9 will be set as NULL which is incorrect.  We can’t set the 

correct nextRight, because when we set nextRight of 9, we only have nextRight of node 4 and ancestors 

of node 4, we don’t have nextRight of nodes in right subtree of root.

Solution for BTs which are not complete

Method 3:Modified Pre Order with nextRight

In the method 2 we traversed the nodes in pre order fashion. 

Instead of traversing in Pre Order fashion (root, left, 
right), if we traverse the nextRight node before the left and right 
children (root, nextRight, left), then we can make sure that all nodes 
at level i have the nextRight set, before the level i+1 nodes.  Let us 
consider the following example.In the above example,

The method 2 fails for right child of node 4.In this method, we make
sure that all nodes at the 4′s level (level 2) have nextRight set, 
before we try to set the nextRight of 9.  So when we set the nextRight 
of 9, we search for a nonleaf node on right side of node 4 
(getNextRight() does this for us). 

Code:

#include <stdio.h>
#include <stdlib.h>

struct node
{
  int data;
  struct node *left;
  struct node *right;
  struct node *nextRight;
};

typedef struct node* Node;

//Method 2

void connectRecur(struct node* p);

void connect_pre (struct node *p)
{
    p->nextRight = NULL;

    connectRecur(p);
}

void connectRecur(struct node* p)
{
  if (!p)
    return;

  // Set the nextRight pointer for p's left child
  if (p->left)
    p->left->nextRight = p->right;

  // Set the nextRight pointer for p's right child
  // p->nextRight will be NULL if p is the right most child at its level
  if (p->right)
    p->right->nextRight = (p->nextRight)? p->nextRight->left: NULL;

  // Set nextRight for other nodes in pre order fashion
  connectRecur(p->left);
  connectRecur(p->right);
}

//Method 1


void connect_Naive(Node p) {
  if (p == NULL)
    return;
  if (p->left == NULL || p->right == NULL)
    return;
  Node rightSibling;
  Node p1 = p;
  while (p1) {
    if (p1->nextRight)
      rightSibling = p1->nextRight->left;
    else
      rightSibling = NULL;
    p1->left->nextRight = p1->right;
    p1->right->nextRight = rightSibling;
    p1 = p1->nextRight;
  }
  connect_Naive(p->left);
}

//Method 3

void connectRecur_BT(struct node* p);
struct node *getNextRight(struct node *p);

void connect_BT (struct node *p)
{
    p->nextRight = NULL;

    connectRecur_BT(p);
}

/* Set next right of all descendents of p. This function makes sure that
nextRight of nodes ar level i is set before level i+1 nodes. */
void connectRecur_BT(struct node* p)
{
    // Base case
    if (!p)
       return;

    /* Before setting nextRight of left and right children, set nextRight
    of children of other nodes at same level (because we can access
    children of other nodes using p's nextRight only) */
    if (p->nextRight != NULL)
       connectRecur_BT(p->nextRight);

    /* Set the nextRight pointer for p's left child */
    if (p->left)
    {
       if (p->right)
       {
           p->left->nextRight = p->right;
           p->right->nextRight = getNextRight(p);
       }
       else
           p->left->nextRight = getNextRight(p);

       /* Recursively call for next level nodes.  Note that we call only
       for left child. The call for left child will call for right child */
       connectRecur_BT(p->left);
    }

    /* If left child is NULL then first node of next level will either be
      p->right or getNextRight(p) */
    else if (p->right)
    {
        p->right->nextRight = getNextRight(p);
        connectRecur_BT(p->right);
    }
    else
       connectRecur_BT(getNextRight(p));
}

/* This function returns the leftmost child of nodes at the same level as p.
   This function is used to getNExt right of p's right child
   If right child of p is NULL then this can also be used for the left child */
struct node *getNextRight(struct node *p)
{
    struct node *temp = p->nextRight;

    /* Traverse nodes at p's level and find and return
       the first node's first child */
    while(temp != NULL)
    {
        if(temp->left != NULL)
            return temp->left;
        if(temp->right != NULL)
            return temp->right;
        temp = temp->nextRight;
    }

    // If all the nodes at p's level are leaf nodes then return NULL
    return NULL;
}

struct node* newnode(int data)
{
  struct node* node = (struct node*)
                       malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;
  node->nextRight = NULL;

  return(node);
}

int main()
{

  /* Constructed binary tree is
            10
          /   \
        8      2
      /
    3
  */
  struct node *root = newnode(10);
  root->left        = newnode(8);
  root->right       = newnode(2);
  root->left->left  = newnode(3);
  

  struct node *root1 = newnode(10);
  root1->left        = newnode(8);
  root1->right       = newnode(2);
  root1->left->left  = newnode(3);
  root1->right->right       = newnode(90);


  connect_pre(root);
//connect_Naive(root);
  connect_BT(root1);

  // Let us check the values of nextRight pointers
  printf("Following are populated nextRight pointers in the tree "
          "(-1 is printed if there is no nextRight) \n");
  printf("nextRight of %d is %d \n", root->data,
         root->nextRight? root->nextRight->data: -1);
  printf("nextRight of %d is %d \n", root->left->data,
        root->left->nextRight? root->left->nextRight->data: -1);
  printf("nextRight of %d is %d \n", root->right->data,
        root->right->nextRight? root->right->nextRight->data: -1);
  printf("nextRight of %d is %d \n", root->left->left->data,
        root->left->left->nextRight? root->left->left->nextRight->data: -1);

  //Incomplete BT

  printf("\n");
  
  /*
  Constructed binary tree is
              10
            /   \
          8      2
        /         \
      3            90
  
  */

  printf("Following are populated nextRight pointers in the tree "
          "(-1 is printed if there is no nextRight) \n");
  printf("nextRight of %d is %d \n", root1->data,
         root1->nextRight? root1->nextRight->data: -1);
  printf("nextRight of %d is %d \n", root1->left->data,
        root1->left->nextRight? root1->left->nextRight->data: -1);
  printf("nextRight of %d is %d \n", root1->right->data,
        root1->right->nextRight? root1->right->nextRight->data: -1);
  printf("nextRight of %d is %d \n", root1->left->left->data,
        root1->left->left->nextRight? root1->left->left->nextRight->data: -1);

  getchar();
  return 0;
}

Method 4:Iterative Approach

In the iterative version, we use nested loop. The outer loop, goes 
through all the levels and the inner loop goes through all the nodes at 
every level.  This solution uses constant space.

Code:

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node *left;
    struct node *right;
    struct node *nextRight;
};

/* This function returns the leftmost child of nodes at the same level as p.
   This function is used to getNExt right of p's right child
   If right child of is NULL then this can also be sued for the left child */
struct node *getNextRight(struct node *p)
{
    struct node *temp = p->nextRight;

    /* Traverse nodes at p's level and find and return
       the first node's first child */
    while (temp != NULL)
    {
        if (temp->left != NULL)
            return temp->left;
        if (temp->right != NULL)
            return temp->right;
        temp = temp->nextRight;
    }

    // If all the nodes at p's level are leaf nodes then return NULL
    return NULL;
}

/* Sets nextRight of all nodes of a tree with root as p */
void connect(struct node* p)
{
    struct node *temp;

    if (!p)
      return;

    // Set nextRight for root
    p->nextRight = NULL;

    // set nextRight of all levels one by one
    while (p != NULL)
    {
        struct node *q = p;

        /* Connect all childrem nodes of p and children nodes of all other nodes
          at same level as p */
        while (q != NULL)
        {
            // Set the nextRight pointer for p's left child
            if (q->left)
            {
                // If q has right child, then right child is nextRight of
                // p and we also need to set nextRight of right child
                if (q->right)
                    q->left->nextRight = q->right;
                else
                    q->left->nextRight = getNextRight(q);
            }

            if (q->right)
                q->right->nextRight = getNextRight(q);

            // Set nextRight for other nodes in pre order fashion
            q = q->nextRight;
        }

        // start from the first node of next level
        if (p->left)
           p = p->left;
        else if (p->right)
           p = p->right;
        else
           p = getNextRight(p);
    }
}

/* UTILITY FUNCTIONS */
/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newnode(int data)
{
    struct node* node = (struct node*)
                        malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    node->nextRight = NULL;

    return(node);
}

/* Driver program to test above functions*/
int main()
{

    /* Constructed binary tree is
              10
            /   \
          8      2
        /         \
      3            90
    */
    struct node *root = newnode(10);
    root->left        = newnode(8);
    root->right       = newnode(2);
    root->left->left  = newnode(3);
    root->right->right       = newnode(90);

    // Populates nextRight pointer in all nodes
    connect(root);

    // Let us check the values of nextRight pointers
    printf("Following are populated nextRight pointers in the tree "
           "(-1 is printed if there is no nextRight) \n");
    printf("nextRight of %d is %d \n", root->data,
           root->nextRight? root->nextRight->data: -1);
    printf("nextRight of %d is %d \n", root->left->data,
           root->left->nextRight? root->left->nextRight->data: -1);
    printf("nextRight of %d is %d \n", root->right->data,
           root->right->nextRight? root->right->nextRight->data: -1);
    printf("nextRight of %d is %d \n", root->left->left->data,
           root->left->left->nextRight? root->left->left->nextRight->data: -1);
    printf("nextRight of %d is %d \n", root->right->right->data,
           root->right->right->nextRight? root->right->right->nextRight->data: -1);

    getchar();
    return 0;
}

Tree Traversal -IV

Question 1: Traverse inorder without recursion and without stack
Question 2:
Given an array that stores a complete Binary Search Tree, write a function that efficiently prints the given array in ascending order. For example, given an array [4, 2, 5, 1, 3], the function should print 1, 2, 3, 4, 5
                                                                            4
                                                                   /                \
                                                               2                    5
                                                          /        \
                                                       1           3

Morris Inorder traversal:

The idea of Morris Traversal is based on Threaded Binary Tree. In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree.


           8
          /   \
        5      17
      /  \
    2     7

For above tree When we are are at 8 we find inorder predecessor of 8 =7 and point right of 7 to 8.When we are at 5 we point right of 2 to 5 [ as 5 in inorder successor of 2].We also restore the tree when we come back from 2 to 5 using right of 2.


The algorithm for Morris traversal is

    Initialize current as root
    While current is not NULL
        If current does not have left child
            Print current's data
            Go to the right, i.e., current = current->right
        Else
            Make current as right child of the rightmost node in current's left sub-tree
            Go to this left child, i.e., current = current->left

Code:

#include<stdio.h>
#include<stdlib.h>

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

void MorrisTraversal(struct tNode *root)
{
  struct tNode *current,*pre;

  if(root == NULL)
     return;

  current = root;
  while(current != NULL)
  {
    if(current->left == NULL)
    {
      printf(" %d ", current->data);
      current = current->right;
    }
    else
    {
      /* Find the inorder predecessor of current */
      pre = current->left;
      while(pre->right != NULL && pre->right != current)
        pre = pre->right;

      /* Make current as right child of its inorder predecessor */
      if(pre->right == NULL)
      {
        pre->right = current;
        current = current->left;
      }

      /* Revert the changes made in if part to restore the original
        tree i.e., fix the right child of predecssor */
      else
      {
        pre->right = NULL;
        printf(" %d ",current->data);
        current = current->right;
      } /* End of if condition pre->right == NULL */
    } /* End of if condition current->left == NULL*/
  } /* End of while */
}


struct tNode* newtNode(int data)
{
  struct tNode* tNode = (struct tNode*)
                       malloc(sizeof(struct tNode));
  tNode->data = data;
  tNode->left = NULL;
  tNode->right = NULL;

  return(tNode);
}


int main()
{

  /* Constructed binary tree is
            8
          /   \
        5      17
      /  \
    2     7
  */
  struct tNode *root = newtNode(8);
  root->left        = newtNode(5);
  root->right       = newtNode(17);
  root->left->left  = newtNode(2);
  root->left->right = newtNode(7);

  MorrisTraversal(root);

  getchar();
  return 0;
}

Sorted order printing

Strategy:Inorder traversal of BST prints it in ascending order. The only trick is to modify recursion termination condition in standard Inorder Tree Traversal.

void printSorted(int arr[], int start, int end)

{

  if(start > end)

    return;

  // print left subtree

  printSorted(arr, start*2 + 1, end);

  printf("%d  ", arr[start]);

  // print right subtree

  printSorted(arr, start*2 + 2, end);

}

Time Complexity:O(n)

Remove Duplicate nodes in BST/BT

Write A Program to Remove Duplicates from BST.

Strategy:

Assuming if duplicate is there in inserting in a BST we put that in the left.
So 2 cases are there :
1.duplicate is the left child of its replica.
2.duplicate is at the successor position of the node.

Pseudo Code:

func(Node *node)
  {
    if(!node)
    return;

if(isduplicateexist(node))
   {
    dupparent=find_dup_parent(node);
    if(dupparent ! =node)
      {
       dup=dupparent->right;
      dupparent->right=dupparent->right->left;
      }
  else
   {
    dup=node->left;
    node->left=node->left->left;
   }

del (dup);
}
func(node->left);
func(node->right);
}

Remove Duplicates from BT.
http://www.mycareerstack.com/question/155/

Pending

Pending

IdenticalTree(), mirrorTree(), isFoldableTree() and isSumTree()

Same Tree:

Given two binary trees, return true if they are structurally identical -- they are made of nodes with the same values arranged in the same way

http://www.geeksforgeeks.org/write-c-code-to-determine-if-two-trees-are-identical/
http://www.geeksforgeeks.org/iterative-function-check-two-trees-identical/

int sameTree(struct node* a, struct node* b) { 

int sameTree(struct tree* a, struct tree* b)
{

    if (a==NULL && b==NULL)
        return 1;
    else if (a!=NULL && b!=NULL)
   {
        return
        (
            a->data == b->data &&
           sameTree(a->left, b->left) &&
           sameTree(a->right, b->right)
        );
    }
    else return 0;
}
Time Complexity:
Complexity of the identicalTree() will be according to the tree with lesser number of nodes. Let number of nodes in two trees be m and n then complexity of sameTree() is O(m) where m < n.

Iterative solution:

If they are binary search trees then you can do any kind of traversal such as inorder, preorder etc, in case of a general tree we can do a breadth first traversal from left most to right most child of a node and if that is same then the two trees are identical.

Mirror Tree
Change a tree so that the roles of the left and right pointers are swapped at every node.
So the tree...
       4
      / \
     2   5
    / \
   1   3

 is changed to...
       4
      / \
     5   2
        / \
       3   1

void mirror(struct tree* root)

{

  if (root==NULL)

    return;

  else

  {

    struct node* temp;

    mirror(root->left);

    mirror(root->right);

    temp        = root->left;

    root->left  = root->right;

    root->right = temp;

  }

}

Time Complexity:O(n)
Auxiliary Space : If we don’t consider size of stack for function calls then O(1) otherwise O(n).

Fold-able Tree:

Given a binary tree,find whether it can be foldable or not :

A tree can be folded if left and right subtrees of the tree are structure wise mirror image of each other. An empty tree is considered as foldable.

Method 1:Without Mirroring
There are mainly two functions:
// Checks if tree can be folded or not

IsFoldable(root)
1) If tree is empty then return true
2) Else check if left and right subtrees are structure wise mirrors of
    each other. Use utility function IsFoldableUtil(root->left,
    root->right) for this.

// Checks if n1 and n2 are mirror of each other.

IsFoldableUtil(n1, n2)
1) If both trees are empty then return true.
2) If one of them is empty and other is not then return false.
3) Return true if following conditions are met
   a) n1->left is mirror of n2->right
   b) n1->right is mirror of n2->left




Code:

bool IsFoldable(struct node *root)

{

     if (root == NULL)

     {  return true;  }

     return IsFoldableUtil(root->left, root->right);

}

bool IsFoldableUtil(struct node *n1, struct node *n2)

{

    if (n1 == NULL && n2 == NULL)

    {  return true;  }

    if (n1 == NULL || n2 == NULL)

    {  return false; }

    return IsFoldableUtil(n1->left, n2->right) &&

           IsFoldableUtil(n1->right, n2->left);

}

Method 2:Mirroring Tree

1) If tree is empty, then return true.
2) Convert the left subtree to its mirror image
    mirror(root->left);
3) Check if the structure of left subtree and right subtree is same
   and store the result.
    res = isStructSame(root->left, root->right); /*isStructSame()
        recursively compares structures of two subtrees and returns
        true if structures are same */
4) Revert the changes made in step (2) to get the original tree.
    mirror(root->left);
5) Return result res stored in step 2.

Code:

bool isFoldable(struct node *root)

{

  bool res;

  if(root == NULL)

    return true;

  mirror(root->left);

  res = isStructSame(root->left, root->right);

  mirror(root->left);

  return res;

}

bool isStructSame(struct node *a, struct node *b)

{

  if (a == NULL && b == NULL)

  {  return true; }

  if ( a != NULL && b != NULL &&

       isStructSame(a->left, b->left) &&

       isStructSame(a->right, b->right)

     )

  {  return true; }

  return false;

}

void mirror(struct node* node)

{

  if (node==NULL)

    return;

  else

  {

    struct node* temp;

    mirror(node->left);

    mirror(node->right);

    temp        = node->left;

    node->left  = node->right;

    node->right = temp;

  }

}

Time complexity: O(n)

Sum Tree:
http://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-sumtree/
http://www.geeksforgeeks.org/convert-a-given-tree-to-sum-tree/
http://www.geeksforgeeks.org/check-for-children-sum-property-in-a-binary-tree/
http://www.geeksforgeeks.org/convert-an-arbitrary-binary-tree-to-a-tree-that-holds-children-sum-property/
http://www.geeksforgeeks.org/transform-bst-sum-tree/

Double Tree:
For each node in a binary search tree, create a new duplicate node, and insert the duplicate as the left child of the original node. The resulting tree should still be a binary search tree.
So the tree...
    2
   / \
  1   3

 is changed to...
       2
      / \
     2   3
    /   /
   1   3
  /
 1
Concept:
Recursively convert the tree to double tree in postorder fashion. For each node, first convert the left subtree of the node, then right subtree, finally create a duplicate node of the node and fix the left child of the node and left child of left child.
Code:

void doubleTree(struct node* node)

{

  struct node* oldLeft;

  if (node==NULL) return;

  doubleTree(node->left);

  doubleTree(node->right);

  oldLeft = node->left;

  node->left = newNode(node->data);

  node->left->left = oldLeft;

}
Time Complexity: O(n) where n is the number of nodes in the tree.