Tuesday, 17 September 2013

Binary Search Tree Interview Questions

HTML Online Editor Sample

 

#include<stdio.h>

#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<malloc.h>
#include<stack>
 
class bst
{
private:
 
struct bnode
{
bnode *left;
bnode* right;
int key;
}*root;
 
struct snode
{
bnode * input;
snode * next;
}*top;
struct qnode
{
bnode *input;
qnode * next;
}*front;
 
 
public:
bst();
void insert(bnode * &root,int key);
void insertintotree(int key);
void search(bnode * root,int key);
void searchintree(int key);
int find_max(bnode* root);
void delete_node(bnode *&root,int &key);
void deletenodefromtree(int key);
 
void remove(bnode * root);
void mirror(bnode * root);
void maketreemirror();
void heightoftree();
int size();
void scan(bnode * root,int &count);
void lca(bnode* root,int key1,int key2);
void leastcommonancestorofkey(int key1,int key2);
void printinorder();
void printpreorder();
void printpostorder();
void inorder(bnode * root);
void preorder(bnode * root);
void postorder(bnode * root);
int height_tree(bnode *root);
void root_to_leaf(bnode *root);
void printroottoleafpath();
void push(bnode *root);
void pop();
void print_stack(snode *top);
void pathfromroottoleaf();
void print_ancestor(bnode * root,int key);
void printancestoroftree(int key);
 
void print_key(bnode * root,int key1,int key2);
void print_inorder(bnode * root,int key1,int key2);
void printdatabetweentwokey(int key1,int key2);
void kth_smallest(bnode *root,int k,int &count);
void kthsmallestintree(int key);
int get_level(bnode * root,int key);
void getlevelofkey(int key);
void level_order();
void inqueue(bnode * root);
void * dqueue();
bool isempty();
void reverse_level_order();
void leaf_count(bnode* root,int &count);
void totalnoofleaf();
//bool isbst(bnode *root1,bnode *root2);
//bool children_sum_property(bnode* root);
//int diameter(bnode *root);
//void convert_children_sum_tree(bnode* root);
void level_order_spiral();
bool isheight_balanced(bnode* root);
void isheightbalancedtree();
//void inorder_without_recursion();
//void inorder_witout_stack();
//bool is_triplet_zero(bnode* root);
//bool find_sum(int key1,int key2);
//void list_to_tree();
//void tree_to_list();
//void iterative_preorder();
//void iterative_postorder();
~bst();
};
 
bst::bst()
{
 
root=NULL;
top=NULL;
front=NULL;
 
}
int max(int a,int b)
{
 
if(a>=b)
return a;
else return b;
}
 
 
void bst::insert(bnode * &root,int key)
{
if(root==NULL)
{
 
root=new bnode;
root->key=key;
root->left=NULL;
root->right=NULL;
printf("\n Insterted\n");
return;
}
 
if(root->key>key)
insert(root->left,key);
else if(root->key<key)
insert(root->right,key);
else
printf("\n key already present\n");
}
void bst::insertintotree(int key)
{
insert(root,key);
}
void bst::maketreemirror()
{
 
mirror(root);
}
void bst::search(bnode *root,int key)
{
if(root==NULL)
return ;
if(root->key==key)
{
 
printf("\nkey found \n");
 
return ;
}
if(root->key>key)
search(root->left,key);
else if(root->key<key)
search(root->right,key);
 
}
 
 
void bst::searchintree(int key)
{
search(root,key);
 
}
void bst::mirror(bnode *root)
{
if(root==NULL)
return;
bnode* temp=root->left;
root->left=root->right;
root->right=temp;
mirror(root->left);
mirror(root->right);
return;
 
 
}
 
 
void bst::heightoftree()
{
printf("\n the height of the tree is %d \n",height_tree(root));
 
}
int bst::size()
{
int count=0;
scan(root,count);
printf("  size is %d",count); 
 
}
void bst::scan(bnode * root,int &count)
{
if(root==NULL)
return;
count++;
scan(root->left,count);
scan(root->right,count);
 
}
void bst::inorder(bnode * root)
{
if(root==NULL)
return;
inorder(root->left);
printf(" -> %d ",root->key);
inorder(root->right);
}
void bst:: printinorder()
{
printf("\n *********************inorder travasal ****************\n");
inorder(root);
}
 
 
void bst :: preorder(bnode *root)
{
if(root==NULL)
return ;
printf(" -> %d ",root->key);
preorder(root->left);
preorder(root->right);
}
 
 
 
void bst::printpreorder()
{
printf("\n *********************preorder travasal ****************\n");
preorder(root);
}
 
 
void bst::postorder(bnode* root)
{
if(root==NULL)
return ;
postorder(root->left);
postorder(root->right);
printf(" -> %d ",root->key);
}
 
void bst::printpostorder()
{
printf("\n *********************postorder travasal ****************\n");
postorder(root);
}
 
 
 
int bst::height_tree(bnode * root)
{
if(root==NULL) return -1;
return 1+max(height_tree(root->left),height_tree(root->right));
 
}
 
 
 
void bst:: pathfromroottoleaf()
{
root_to_leaf(root);
 
}
 
void bst::print_ancestor(bnode *root,int key)
{
if(root==NULL)
return;
if(root->key==key)
return;
printf(" %d -> ",root->key);
if(key<root->key)
print_ancestor(root->left,key);
else
print_ancestor(root->right,key);
}
void bst::printancestoroftree(int key)
{
print_ancestor(root,key);
}
 
void bst::kth_smallest(bnode *root,int k,int &count)
{
if(root==NULL)
return ;
kth_smallest(root->left,k,count);
if(count+1==k)
{
printf("\n %d smallest  key is %d \n",k,root->key);
count=100000000;
return ;
}
count++;
kth_smallest(root->right,k,count);
 
}
void bst::kthsmallestintree(int k)
{
int count=0;
kth_smallest(root,k,count);
}
int bst::get_level(bnode *root,int key)
{
if(root==NULL)
return -100000;
if(root->key==key)
return 1;
if(root->key>key)
return 1+get_level(root->left,key);
else
return 1+get_level(root->right,key);
 
}
void bst::getlevelofkey(int key)
{
printf(" the key %d is at %d level",key,get_level(root,key));
}
 
 
void bst::leaf_count(bnode *root,int &count)
{
if(root==NULL)
{
count++;
return ;
}
leaf_count(root->left,count);
leaf_count(root->right,count); 
 
}
void bst::totalnoofleaf()
{
 
int count=0;
leaf_count(root,count);
printf("\n Total No Of Leaf in The tree is %d \n",count);
 
 
}
 
void bst::lca(bnode *root,int key1,int key2)
{
if(root==NULL)
return;
if(root->key>=key1&&root->key<=key2)
{printf(" \n The LCA is %d\n",root->key);
return ;
}
else if(root->key<key1)
return lca(root->right,key1,key2);
else
return lca(root->left,key1,key2);
 
 
}
void bst::leastcommonancestorofkey(int key1,int key2)
{
if(key2>key1)
lca(root,key1,key2);
else
lca(root,key2,key1);
}
 
bool bst::isheight_balanced(bnode* root)
{
if(root==NULL)
return true;
if(isheight_balanced(root->left)&&isheight_balanced(root->right)){
if(abs(height_tree(root->left)-height_tree(root->right))<=0)
return true;
else return false;
}
 
}
void bst::isheightbalancedtree()
{
if(isheight_balanced(root))
printf("\n Height Balanced\n");
else
printf("\n Not height Balanced\n");
}
 
void bst::remove(bnode *root)
{
if(root==NULL)
return;
remove(root->left);
remove(root->right);
delete(root);
 
}
 
int bst::find_max(bnode *root)
{
while(root->right!=NULL)
root=root->right;
return root->key;
 
}
void bst::delete_node(bnode* &root,int &key)
{
 
 
if(root==NULL)
return;
 
if(root->key==key)
{
if(root->left!=NULL&&root->right!=NULL)
{
root->key=find_max(root->left);
delete_node(root->left,root->key);
 
}
 
else
{
 
bnode *t=root;
root=(root->left!=NULL)?root->left:root->right;
delete t;
return;
}
 
}
 
if(key<root->key)
delete_node(root->left,key);
else if(root->key<key)
delete_node(root->right,key);
 
 
 
}
 
void bst::deletenodefromtree(int key)
{
delete_node(root,key);
}
 
void bst:: print_stack(snode *t)
{
if(t==NULL)
return;
print_stack(t->next);
printf(" -> %d ",t->input->key);
 
}
void bst::pop()
{
if(top==NULL)
return;
snode *t=top;
top=top->next;
delete t;
return ;
}
 
void bst::push(bnode *root)
{
if(top==NULL)
{
top=new snode;
top->next=NULL;
top->input=root;
return;
}
snode *t;
t=new snode;
t->input=root;
t->next=top;
top=t;
return;
 
}
 
void bst::print_inorder(bnode * root,int key1,int key2)
{
if(root==NULL)
return;
if(root->key>=key1&&root->key<=key2)
push(root);
if(root->key>=key2)
{print_inorder(root->left,key1,key2);return;}
 
if(root->key<=key1)
{print_inorder(root->right,key1,key2);return;}
print_inorder(root->left,key1,key2);
print_inorder(root->right,key1,key2);
 
 
}
void bst::print_key(bnode *root,int key1,int key2)
{
 
 
if(root->key<key1)
print_key(root->right,key1,key2);
else if(root->key>key2)
print_key(root->left,key1,key2);
 
if(key1<=root->key&&key2>=root->key)
{
print_inorder(root,key1,key2);
print_stack(top);
//push(root);
}
 
 
}
 
void bst::printdatabetweentwokey(int key1,int key2)
{
if(key1<=key2)
print_key(root,key1,key2);
else
print_key(root,key2,key1);
}
void bst::root_to_leaf(bnode* root)
{
 
if(root->left==NULL&&root->right==NULL)
{
printf("\n");
push(root);
print_stack(top);
printf("\n");
pop();
return;
 
 
 
}
push(root);
if(root->left!=NULL)
root_to_leaf(root->left);
if(root->right!=NULL)
root_to_leaf(root->right);
pop();
 
/*
 
if(root->left==NULL&&root->right==NULL)
{
push(root);
printf("\n");
print_stack(top);
printf("\n");
pop();
return;
}
push(root);
if(root->left!=NULL)
{
root_to_leaf(root->left);}
 
if(root->right!=NULL)
{root_to_leaf(root->right);}
 
pop();*/
}
void bst::printroottoleafpath()
{
 
root_to_leaf(root);
}
bool bst::isempty()
{
 
if(front==NULL)
return true;
else
return false;
}
 
void bst::inqueue(bnode * root)
{
if(front==NULL)
{
 
 
front=new qnode;
front->input=root;
front->next=NULL;
return;
}
qnode *t=front;
 
 while(t->next!=NULL)
t=t->next;
qnode *p=new qnode;
p->input=root;
p->next=NULL;
t->next=p;
return;
 
}
 
void* bst::dqueue()
{
if(front==NULL)
{
return NULL;
}
qnode *t=front;
front=front->next;
bnode * node=t->input;
delete t;
return node;
 
 
}
void bst::level_order()
{
 
if(root==NULL)
return;
int count=0;
int level=1;
inqueue(root);
while(!isempty())
{
bnode *t=(bnode*)dqueue();
level--;
printf(" - %d",t->key);
if(t->left!=NULL)
{
inqueue(t->left);
count++;
}
if(t->right!=NULL)
{inqueue(t->right);
 
count++;
}
 
if(level==0)
{
level=count;
count=0;
printf("\n");
}
}
 
 
}
void bst::reverse_level_order()
{
 
if(root==NULL)
return;
int count=0;
int level=1;
inqueue(root);
while(!isempty())
{
bnode *t=(bnode*)dqueue();
level--;
printf(" - %d",t->key);
 
if(t->right!=NULL)
{inqueue(t->right);
 
count++;
}
if(t->left!=NULL)
{
inqueue(t->left);
count++;
}
 
if(level==0)
{
level=count;
count=0;
printf("\n");
}
}
 
 
}
void bst::level_order_spiral()
{
 
if(root==NULL)
return;
stack<struct bnode*> s1;
stack<struct bnode*> s2;
s1.push(root);
while(!s1.empty()||!s2.empty())
{
while(!s1.empty())
{
bnode *t=s1.top();
printf(" -> %d",t->key);
s1.pop();
if(t->right!=NULL)
s2.push(t->right);
if(t->left!=NULL)
s2.push(t->left);
 
 
}
while(!s2.empty())
{
bnode *t=s2.top();
printf(" -> %d",t->key);
s2.pop();
if(t->left!=NULL)
s1.push(t->right);
if(t->right!=NULL)
s1.push(t->right);
}
 
}
}
bst::~bst()
{
 
remove(root);
}
int main()
{
 
bst b;
b.insertintotree(4);
b.insertintotree(2);
b.insertintotree(3);
b.insertintotree(10);
b.insertintotree(1);
b.insertintotree(9);
b.insertintotree(5);
b.insertintotree(7);
b.insertintotree(6);
b.insertintotree(8);
 
//b.maketreemirror();
//b.heightoftree();
//b.size();
//b.printinorder();
//b.printpreorder();
//b.printpostorder();
//b.searchintree(11);
/**************************************b.pathfromroottoleaf();*/
//b.printancestoroftree(7);
//b.kthsmallestintree(6);
//b.getlevelofkey(8);
//b.totalnoofleaf();
//b.leastcommonancestorofkey(9,3);
//b.isheightbalancedtree();
//b.deletenodefromtree(4);
//b.printinorder();
//b.printroottoleafpath();
//b.printdatabetweentwokey(2,10);
//b.reverse_level_order();
b.level_order_spiral();
printf("\n");
return 0;
}
Posted by at

2 comments:

Subscribe to: Post Comments (Atom)