violinlakshmi
BAN USERwhat anonymous said is true,but I was not able to come up with a solution for a binary tree. So the following program is assuming a BST and the program is to find the common nodes of the two nodes given.
/*Given 2 nodes in a binary tree (not a binary search tree), find the first common parent node.
You are not allowed to store any nodes in a data structure.*/
#include <stdio.h>
#include <stdlib.h>
struct NODE{
int data;
struct NODE* left;
struct NODE* right;
};
typedef struct NODE* node;
node constructBST(node root,int data){
node cur,mytemp;
if(!root){
node temp;
temp=(node)malloc(sizeof(struct NODE));
temp->data=data;
temp->left=NULL;
temp->right=NULL;
root=temp;
return root;
}
cur=root;
while(cur->data>data){
if(cur->left)
cur=cur->left;
else
break;
}
while(cur->data<=data){
if(cur->right)
cur=cur->right;
else
break;
}
if(data<cur->data){
mytemp=(node)malloc(
sizeof(struct NODE));
mytemp->data=data;
mytemp->left=NULL;
mytemp->right=NULL;
cur->left=mytemp;
}
if(data>cur->data){
mytemp=(node)malloc(
sizeof(struct NODE));
mytemp->data=data;
mytemp->left=NULL;
mytemp->right=NULL;
cur->right=mytemp;
}
return root;
}
int deapth(node root, node node1){
node cur;
int len=0;
if(!root){
printf("\nEmpty list");
return(0);
}
cur=root;
while(node1->data<=cur->data){
if(cur->left){
cur=cur->left;
len++;
}
else
break;
}
while(node1->data>cur->data){
if(cur->right){
cur=cur->right;
len++;
}
else break;
}
return len;
}
node findCommonParent(node root,node node1,node node2){
int data1,data2;
node larger,smaller;
node cur;
cur=root;
if(!cur){
printf("\nEmpty List");
return NULL;
}
data1=node1->data;
data2=node2->data;
if(data1>data2){
larger=node1;
smaller=node2;
}
else{
larger=node2;
smaller=node1;
}
while(cur->data > larger->data){
if(cur->left)
cur=cur->left;
else
break;
}
while(cur->data <= smaller->data){
if(cur->right)
cur=cur->right;
else
break;
}
//printf("\n The common parent is %d ",cur->data);
return cur;
}
int main()
{
int i=0;
node root,commonParent,node1,node2;
commonParent=NULL;
root=NULL;
node1=(node)malloc(sizeof(struct NODE));
node2=(node)malloc(sizeof(struct NODE));
node1->data=1;
node2->data=3;
i=5;
root=constructBST(root,i);
i=2;
root=constructBST(root,i);
i=3;
root=constructBST(root,i);
i=1;
root=constructBST(root,i);
i=9;
root=constructBST(root,i);
i=7;
root=constructBST(root,i);
i=11;
root=constructBST(root,i);
commonParent=findCommonParent(root,node1,node2);
printf("\n The common parent is %d \n",commonParent->data);
return 0;
}
/*Design an algorithm to find the kth number divisible by only 3 or 5 or 7
i.e the only factors of these numbers should be 3,5 and 7.*/
#include<stdio.h>
#include<stdlib.h>
#define MAX_INT 50
void findKthNum(){
int shudPrint=1;
int i=1;
int num=1;
while(num<MAX_INT){
shudPrint=1;
for(i=1;i<=num;i++)
{
if(i==5||i==7||i==3){
if(num%i==0)
shudPrint*=-1;
}
else
shudPrint*=1;
}
if(shudPrint<0){
printf("\n The number is %d",num);
}
num++;
}
return;
}
int main()
{
findKthNum();
return(0);
}
/*Design an algorithm to find the kth number divisible by only 3 or 5 or 7
i.e the only factors of these numbers should be 3,5 and 7.*/
#include<stdio.h>
#include<stdlib.h>
#define MAX_INT 50
void findKthNum(){
int shudPrint=1;
int i=1;
int num=1;
while(num<MAX_INT){
shudPrint=1;
for(i=1;i<=num;i++)
{
if(i==5||i==7||i==3){
if(num%i==0)
shudPrint*=-1;
}
else
shudPrint*=1;
}
if(shudPrint<0){
printf("\n The number is %d",num);
}
num++;
}
return;
}
int main()
{
findKthNum();
return(0);
}
/*
The number is 3
The number is 5
The number is 6
The number is 7
The number is 9
The number is 10
The number is 12
The number is 14
The number is 18
The number is 20
The number is 24
The number is 25
The number is 27
The number is 28
The number is 33
The number is 36
The number is 39
The number is 40
The number is 48
The number is 49
Press any key to continue . . .
*/
/*Give a very good method to count the number of ones in a "n" (e.g. 32) bit number.
- violinlakshmi August 15, 2008(in lg(n) or constant time if possible)*/
#include<stdio.h>
#include<stdlib.h>
int numberOfOnes(unsigned int number){
int count=0;
while(number>0){
if(number&1)
count++;
number=number>>1;
}
return count;
}
int main()
{
int num=9,count=0;
count=numberOfOnes(num);
printf("\nThe number of ones in %d is %d\n",num,count);
return(0);
}