Common Nodes in Two BSTs
Problem Overview
Inorder traversal of a BST visits values in sorted order, so the common nodes are exactly the intersection of two sorted streams.
Intuition
Inorder traversal of a BST visits values in sorted order, so the common nodes are exactly the intersection of two sorted streams. Instead of writing both streams into arrays, two stacks walk the trees together. Each stack always holds the path down to the next unread inorder node. The tops are compared like the merge step of two sorted lists. Equal tops are common values and both sides advance into their right subtrees. When one top is smaller, only that side advances. The walk stops when either stack runs out, because no further matches are possible. Only O(height) nodes sit on each stack at once.
Algorithm
- 1Push every left child from the first root onto the first stack, and do the same for the second root.
- 2While both stacks are nonempty, compare their top nodes.
- 3If the values match, append the value to the answer, pop both tops, and continue from their right children.
- 4If the first top is smaller, pop it and continue from its right child while leaving the second side still.
- 5Otherwise pop the second top and continue from its right child.
- 6Return the collected values, which are already sorted.
Example Walkthrough
Input: r1 = [5, 1, 10, 0, 4, 7, 9], r2 = [10, 7, 20, 4, 9]
- 1. The inorder stream of the first tree begins 0, 1, 4, 5, 7, 9, 10.
- 2. The inorder stream of the second tree begins 4, 7, 9, 10, 20.
- 3. Merging those streams keeps the shared values 4, 7, 9, and 10.
Output: [4, 7, 9, 10]
Common Pitfalls
- • Advance only the smaller side when the tops differ. Advancing both sides would skip a possible later match.
- • After a match, move into both right subtrees. Staying on the same node would duplicate a value or stall.
- • Do not materialize full inorder arrays unless space is not a concern. The two stacks already expose the next sorted values.
- • An empty tree has no common nodes with anything. Stop as soon as either stack is empty.
// Approach: Inorder of a BST is sorted, so the common values are the
// intersection of two sorted streams. Two stacks walk both trees at once,
// always comparing the next inorder nodes. Equal values are kept, the
// smaller side advances, and only O(height) nodes sit on each stack.
// Complexity: O(n + m) time, O(h1 + h2) extra space.
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
class Node {
public int data;
public Node left;
public Node right;
public Node(int val) {
data = val;
left = right = null;
}
}
class Solution {
public ArrayList<Integer> findCommon(Node r1, Node r2) {
ArrayList<Integer> ans = new ArrayList<>();
Deque<Node> s1 = new ArrayDeque<>();
Deque<Node> s2 = new ArrayDeque<>();
while (true) {
while (r1 != null) {
s1.push(r1);
r1 = r1.left;
}
while (r2 != null) {
s2.push(r2);
r2 = r2.left;
}
if (s1.isEmpty() || s2.isEmpty()) {
break;
}
Node a = s1.peek();
Node b = s2.peek();
if (a.data == b.data) {
ans.add(a.data);
s1.pop();
s2.pop();
r1 = a.right;
r2 = b.right;
} else if (a.data < b.data) {
s1.pop();
r1 = a.right;
r2 = null;
} else {
s2.pop();
r2 = b.right;
r1 = null;
}
}
return ans;
}
}