Answer to Question #288895 in C++ for osama

Question

Write a C++ program which should implement a binary search tree using link list. User will provide values as input. Your program should create two Binary Search Tree objects and take values in both of the trees. Now pass the objects to a function which will display the intersection (common nodes) of two trees. Note: Function must be iterative.

Answer 1

#include<iostream>
#include<vector>

using namespace std;

struct Node
{
	int data;
	struct Node *right;
	struct Node *left;
	Node(int _data) :data(_data), left(NULL), right(NULL) {}
};


class BST
{
public:
	struct Node* Insert(struct Node* newNode, struct Node *p)
	{
		if (p == NULL)
		{
			p = newNode;
		}
		else if (newNode->data<p->data)
		{
			p->left = Insert(newNode, p->left);
		}
		else if (newNode->data>p->data)
		{
			p->right = Insert(newNode, p->right);
		}
		return p;
	}


	void Display(struct Node *p)
	{
		if (p == NULL)return;
		cout << p->data << " ";
		Display(p->left);
		Display(p->right);
	}
};



void BSTtoVector(struct Node *p, vector<Node*>& v)
{
	if (p == NULL)return;
	v.push_back(p);
	BSTtoVector(p->left, v);
	BSTtoVector(p->right, v);
}


void Intersection(Node* x, Node* y)
{
	vector<Node*>vecX;
	vector<Node*>vecY;
	BSTtoVector(x, vecX);
	BSTtoVector(y, vecY);
	vector<Node*>::iterator itX, itY;
	cout << endl;
	for (itX = vecX.begin(); itX != vecX.end(); ++itX)
	{
		for (itY = vecY.begin(); itY != vecY.end(); ++itY)
		{
			if (*itX == *itY)
				cout << (*itX)->data << " ";
		}
	}
}


int main()
{
	Node *rootA = new Node(10);
	BST a;
	a.Insert(new Node(5), rootA);
	a.Insert(new Node(3), rootA);
	a.Insert(new Node(8), rootA);
	a.Insert(new Node(4), rootA);
	a.Insert(new Node(6), rootA);
	cout << "Elements of first BST: ";
	a.Display(rootA);


	Node *rootB = new Node(11);
	BST b;
	b.Insert(new Node(7), rootB);
	b.Insert(rootA->left->left, rootB);
	b.Insert(new Node(12), rootB);
	cout << "\nElements of second BST: ";
	b.Display(rootB);
	cout << "\nIntersection is ";
	Intersection(rootA, rootB);
}