Print Common Nodes in Two Binary Search Trees - GeeksforGeeks
Given two Binary Search Trees, find common nodes in them. In other words, find intersection of two BSTs.
We can find common elements in O(n) time and O(h1 + h2) extra space where h1 and h2 are heights of first and second BSTs respectively.
The idea is to use iterative inorder traversal. We use two auxiliary stacks for two BSTs. Since we need to find common elements, whenever we get same element, we print it.
Read full article from Print Common Nodes in Two Binary Search Trees - GeeksforGeeks
Given two Binary Search Trees, find common nodes in them. In other words, find intersection of two BSTs.
We can find common elements in O(n) time and O(h1 + h2) extra space where h1 and h2 are heights of first and second BSTs respectively.
The idea is to use iterative inorder traversal. We use two auxiliary stacks for two BSTs. Since we need to find common elements, whenever we get same element, we print it.
void printCommon(Node *root1, Node *root2){ // Create two stacks for two inorder traversals stack<Node *> stack1, s1, s2; while (1) { // push the Nodes of first tree in stack s1 if (root1) { s1.push(root1); root1 = root1->left; } // push the Nodes of second tree in stack s2 else if (root2) { s2.push(root2); root2 = root2->left; } // Both root1 and root2 are NULL here else if (!s1.empty() && !s2.empty()) { root1 = s1.top(); root2 = s2.top(); // If current keys in two trees are same if (root1->key == root2->key) { cout << root1->key << " "; s1.pop(); s2.pop(); // move to the inorder successor root1 = root1->right; root2 = root2->right; } else if (root1->key < root2->key) { // If Node of first tree is smaller, than that of // second tree, then its obvious that the inorder // successors of current Node can have same value // as that of the second tree Node. Thus, we pop // from s2 s1.pop(); root1 = root1->right; // root2 is set to NULL, because we need // new Nodes of tree 1 root2 = NULL; } else if (root1->key > root2->key) { s2.pop(); root2 = root2->right; root1 = NULL; } } // Both roots and both stacks are empty else break; }}