Check if two binary search trees are identical

Check if two BST’s are identical

In previous posts, we discussed binary search tree and it’s properties, let us solve a problem. Problem statement is : given two binary search tree, find if two binary search trees are identical or equal?¬†For example, below two trees are identical,

binary search trees are identical

where these two trees are not identical.

binary search trees are identical example

How to find if two BSTs are identical?

There is simple but  inefficient solution. First traverse both trees inorder and store it in arrays. Then problem reduces to check if two arrays are equal or not, which can be done in linear time.  Problem with this solution is that it use additional memory and an extra traversal.

Optimized solution is to use divide and conquer. At each node, check if values are same, then problem reduces to check if left subtrees and right subtrees of those nodes are identical. Algorithm is given below.

Algorithm to find if two binary search trees are identical

1. Start from root of both trees
2. If both trees are empty, return true
3. If one of tree is empty and other is not, then return false.
4. Check these three conditions
   4.1 check if root1->value == root2->value, if not return false
   4.2 Check if left subtree of root1 and root2 are equal
   4.3 Check if right subtree of root1 and root2 are equal
5. If all points in step 4 are true, return true else false.

Implementation to check if two binary search trees are identical is quite simple.

Complexity of algorithm to find if two binary search tree are identical or equal is O(N) where N is number of nodes in smaller tree.

Please share if something is wrong or missing, we would love to hear from you. Sharing is caring.