Given two binary trees, find first leaves of two trees that do not match. If there are no non-matching leaves, print nothing.
Input : First Tree 5 / 2 7 / 10 11 Second Tree 6 / 10 15 Output : 11 15 If we consider leaves of two trees in order, we can see that 11 and 15 are the first leaves that do not match.
Method 1 (Simple) :
Do Inorder traversal of both trees one by one, store the leaves of both trees in two different lists. Finally find first values which are different in both lists. Time complexity is O(n1 + n2) where n1 and n2 are number of nodes in two trees. Auxiliary space requirement is O(n1 + n2).
Method 2 (Efficient)
This solution auxiliary space requirement as O(h1 + h2) where h1 and h2 are heights of trees. We do Iterative Preorder traversal of both the trees simultaneously using stacks. We maintain a stack for each tree. For every tree, keep pushing nodes in the stack till the top node is a leaf node. Compare the two top nodes f both the stack. If they are equal, do further traversal else return.
First non matching leaves : 11 15
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.