I am looking for the most optimal in terms of complexity(space and time).
My approach until now is: Traverse one tree in-order and for each nodeId, search that nodeId in second tree.
Node structure:
struct node{
long long nodeId;
node *left;
node *right;
};
Please let me know if any doubts about the question.
Assuming one tree is n long and the other is m long, your approach is O(n*m) long, while you could do it in O(n+m).
Let us say you have to pointers to where you are in each tree (location_1 and location_2). Start going through both trees at the same time, and each time decide which pointer you want to advance. Lets say location_1 is pointing at a node with nodeId = 4 and location_2 is at nodeId = 7. In this case location_1 moves forwards since any node before the one it is looking at has a smaller value then 4.
By "moves forwards" I mean an in-order traverse of the tree.
You can do this with a standard merge in O(n+m) time. The general algorithm is:
n1 = Tree1.Root
n2 = Tree2.Root
while (n1 != NULL && n2 != NULL)
{
if (n1.Value == n2.Value)
{
// node exists in both trees. Advance to next node.
n1 = GetInorderSuccessor(n1)
n2 = GetInorderSuccessor(n2)
}
else if (n1.Value > n2.Value)
{
// n2 is not in Tree1
n2 = GetInorderSuccessor(n2)
}
else
{
// n1 is smaller than n2
// n1 is not in Tree2
n1 = GetInorderSuccessor(n1)
}
}
// At this point, you're at the end of one of the trees
// The other tree has nodes that are not in the other.
while (n1 != NULL)
{
// n1 is not in Tree2. Output it.
// and then get the next node.
n1 = GetInorderSuccessor(n1)
}
while (n2 != NULL)
{
// n2 is not in Tree1. Output it.
// and then get the next node.
n2 = GetInorderSuccessor(n2)
}
The only hard part here is that GetInorderSuccessor call. If you're doing this with a tree, then you'll need to maintain state through successive calls to that function. You can't depend on a standard recursive tree traversal to do it for you. Basically, you need a tree iterator.
The other options is to first traverse each tree to make a list of the nodes in order, and then write the merge to work work with those lists.
Slightly modified Morris Traversal should solve the solution with movement similar to merge part of merge sort. Time Complexity: O(m + n), Space Complexity: O(1).
