Check if two binary trees are identical or not | Iterative & Recursive

Write an efficient algorithm to check if two binary trees are identical or not. i.e. if they have identical structure & their contents are also same.

 


 

The idea is to traverse both trees and compare value at their root node. If the value matches, we recursively check if left subtree of first tree is identical to left subtree of second tree and right subtree of first tree is identical to right subtree of second tree. If the value at their root node differs, the trees violates data property. If at any point in the recursion, the first tree is empty & second tree is non-empty or second tree is empty & first tree is non-empty, the trees violates structural property and they cannot be identical.

 
C++ implementation –
 

Download   Run Complete Code

 


 
Iterative solution –

In iterative version, we make use of stack data structure in similar way as implicit recursive stack.

 
C++ implementation –
 

Download   Run Complete Code

 
The time complexity of both recursive and iterative solution is linear in terms of number of nodes in two trees.
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
irfan
Guest
irfan

provide one or two sample input and output. it will be help ful in understanding.

wpDiscuz