Sunday, April 28, 2013

Right Neighbour of nodes in a Binary Tree

Given a binary tree with nodes that have left, right pointers pointing to the left and right children respoectively. Each node also has a right-neighbor pointer that currently points to null.
Write a function to make it point to its neighbor.

Example:
Input tree
1
2 3
4 5 6 7
Expected configuration of the tree
1 right-neighbour should point to null
2 right-neighbour should point to 3
3 right-neighbour should point to null
4 right-neighbour should point to 5
5 right-neighbour should point to 6
6 right-neighbour should point to 7
7 right-neighbour should point to null

Approach
1. Do a level-order traversal of the binary tree.
2. During this traversal keep track of the current root you visit in a level.
3. The next time you visit a root in the same level, make the right-neighbour pointer of the current root to point to this root.
4. Update the current pointer to this root.

#include<iostream>
using namespace std;
struct node
{
int data;
struct node* left;
struct node* right;
struct node* right_neighbour;
};
struct node* createnode(int x)
{
struct node* new_node=new struct node;
new_node->data=x;
new_node->left=NULL;
new_node->right=NULL;
new_node->right_neighbour=NULL;
return new_node;
}

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

void levelorderprint(struct node* root,int level,struct node** current)
{
if(root && level==0)
{
cout<<root->data<<" ";
if(*current == NULL)
{
*current = root;
}
else
{
(*current)->right_neighbour=root;
*current=root;
}
}
else if(root)
{
levelorderprint(root->left,level-1,current);
levelorderprint(root->right,level-1,current);
}
}
void levelorder(struct node* root)
{
int h=height(root);
struct node* addr=NULL;
struct node** current=&addr;
for(int i=0;i<h;i++)
{
addr=NULL;//Very important step because addr gets changed in the function levelorderprint as its address is passed.
current=&addr;
levelorderprint(root,i,current);
cout<<endl;
}
}

void inorder(struct node* root)
{
if(root)
{
inorder(root->left);
cout<<root->data;
if(!root->right_neighbour)
{
cout<<endl;
}
else
{
cout<<"->"<<root->right_neighbour->data<<endl;
}
inorder(root->right);
}
}

int main()
{
struct node* root1=createnode(1);
root1->left=createnode(2);
root1->right=createnode(3);
root1->left->right=createnode(5);
root1->left->left=createnode(4);
root1->right->right=createnode(7);
root1->right->left=createnode(6);
root1->right->right->left=createnode(8);
cout<<"The input tree is\n";
levelorder(root1);
cout<<"The right neighbours are:\n";
inorder(root1);
}
Output:
1
2 3
4 5 6 7
8
The right neighbours are:
4->5
2->3
5->6
1
6->7
3
8
7

Process returned 0 (0x0)   execution time : 0.056 s
Press any key to continue.

No comments:

Post a Comment