Data Structure Binary Search Tree Interview Question | Problem Solving

Data Structure Binary Search Tree Interview Question | Problem Solving C++ Programming

Question

In this problem you have to write a program to check if two given binary trees are structurally equivalent.

Two trees are structurally equivalent if they are both null or if the left and right children of one are structurally equivalent to the RESPECTIVE children of the other. In other words, when you draw the trees on paper, they should LOOK alike (ignoring the values at the nodes).

Construct a binary search tree with the input in the second line and use this as the basis-tree. For each of the remaining N-1 lines, construct a binary search tree and compare against the basis tree for equivalence. If the trees are equivalent, print YES else print NO. Also print the depth difference between the two trees (ie, depth of the bigger tree minus the depth of the smaller tree). Both these for a given tree pair must be on one line separated by a space.The answers for the different pairs must be on separate lines.

Sample Input/OutputInput
5
1 3 2 4 -1
4 1 2 3 -1
3 2 1 4 -1
4 3 2 1 -1
1 3 4 2 -1
Output
NO 1
NO 0
NO 1
YES 0
(Note that the depth difference will be zero if the trees are equivalent.)

Solution

Step 1 :  First a follow  we need the logic of Binary Search Tree how create binary search tree. So first learn Binary Search tree.

Step 2: For identifying the structure of Binary tree we must know orders of Binary Search Tree like preoder,postorder,inorder etc. I used preorder as this orders used to represent the trees order. So instead of printing the node we can calculate here the structure using the logic of Huffman Coding tree as left node is 0 and right node 1 which will save into sum variable and creating structure. As we have given on structure base so we can't calculate on bases of Values entered so when we detect so left node the we pass own value as 0 and for right 1.

Step 3: Calculating maxHeight of Binary Tree using Recursive function as given in Coding.

Step 4:Create getHeight() function to and calculate difference .

Coding Snippet :-

/* Data Structure Binary Search Tree in C plus plus Program from Nullpointer.in*/

#include<iostream>
using namespace std;

class Node
{
public:
int data;
Node *left,*right;
Node()
{
left=NULL;
right=NULL;
}
Node(int e)
{
data=e;
left=right=NULL;
}
};

class Binary
{

Node *root;

public:
int depth,sum,i;
Binary()
{
root=NULL;
depth=0;
sum=0;
i=0;
}
Binary(Binary &cp)
{}
void insert(int ele)
{
Node *temp=new Node(ele);
int flag=1;
Node *q=root;
while(flag)
{
if(root==NULL)
{
root=temp;
flag=0;

}
else
{
 
 if(q->data>temp->data)//left
 {
     if(q->left==NULL)
     {
     q->left=temp;
     flag=0;
     }
     else
     {
     q=q->left;
     }
 }
 else //right
 {
     if(q->right==NULL)
     {
     q->right=temp;
     flag=0;
     }
     else
     {
     q=q->right;
     }
 
 } 

}
}//while
}//insert

void preorder(Node *node,int dp,int i)
{
    if(node!=NULL)
    {
    depth++;
    sum=sum*10+i;
    preorder(node->left,depth,i=0);
    preorder(node->right,depth,i=1);
    }
}

/*maxHeight function taken from 
"http://www.leetcode.com/2010/04/maximum-height-of-binary-tree.html" */
int maxHeight(Node *node)
 {  
   if (!node)
       { return 0;}
    int left_height = maxHeight(node->left);
    int right_height = maxHeight(node->right); 
    return (left_height > right_height) ? left_height + 1 : right_height + 1;
}

int getHeight()
{
 return maxHeight(root);
}

void display(int d,int i)
{
preorder(root,d,i);
}

};//end class

int main()
{
int btrees;
cin>>btrees;
Binary b[btrees];
Binary basis_tree;
int ip;

for(int i=0;i<btrees;i++)
{
 ip=0;
 while(1)
 {
 cin>>ip;
 if(ip<=-1)
 {break;}
 else
   {b[i].insert(ip);}
 }
}

for(int s=0;s<btrees;s++)
{
b[s].display(0,0);
}
basis_tree=b[0];
for(int j=1;j<btrees;j++)
{

if(basis_tree.sum==b[j].sum)
{
cout<<"YES"<<" "<<b[j].getHeight()-b[0].getHeight()<<endl;
}
else
{
cout<<"NO"<<" "<<b[j].getHeight()-b[0].getHeight()<<endl;
}
}
return 0;
}