Binary search tree Write a function bool comp( const Search_tree<int> x, const S
ID: 3711463 • Letter: B
Question
Binary search tree Write a function
bool comp( const Search_tree<int> x, const Search_tree<int> y)
to compare two binary search trees x, y, that store integer data. If the two trees contain the same set of integers, the function should return true, and false otherwise. Note that two binary search trees could have different topological structure but still contain the same data. You have to write all the methods and functions you need (e.g., if you use a traversal method, you have to write it here). Your function should be computationally efficient.
template <class Record>
class Search_tree: public Binary_tree<Record> {
public:
private: // Add auxiliary function prototypes here.
}
bool comp(const Search_tree<int> x, const Search_tree<int> y) // WRITE THIS FUNCTION
Explanation / Answer
bool comp(const Search_tree<int> x, const Search_tree<int> y)
{
vector<int> arr1;
vector<int> arr2;
// when we traverse the binary search tree in inorder, then the order in which we traverse is in sorted order
// so arr1 and arr2 are both sorted
// traverse x in inorder manner
inorder( x , arr1 );
// traverse y in inorder manner
inorder( y , arr2 );
// if the size of both array is not same
if( arr1.size() != arr2.size() )
return false;
int i;
for( i = 0 ; i < arr1.size() ; i++ )
// if the current element is not same
if( arr1[i] != arr2[i] )
return false;
}
void inorser(const Search_tree<int> x, vector<int> arr)
{
if( x != NULL )
{
// traverse the left subtree
// getLeft() return the pointer to left child
inorder( x.getLeft() , arr );
// add the current element to arr
arr.push_back( x.getData() );
// traverse the right subtree
// getRight() return the pointer to right child
inorder( x.getRight() , arr );
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.