Meta interview question

Compute the intersection of two binary search trees.

Interview Answer

Anonymous

10 Jan 2017

void intersectionBST(Tree* root1, Tree* root2) { stack<div>s1, s2; while(true) { if(root1) { s1.push(root1); root1 = root1->left; } else if(root2) { s2.push(root2); root2=root2->left; } else if(!s1.empty() && !s2.empty()) { root1 = s1.top(); root2 = s2.top(); if(root1->val == root2->val) { coutvalright; root2= root2->right; } else if(root1->val val) { s1.pop(); root1=root1->right; } else { s2.pop(); root2 = root2->right; } } else break; } }</div>