Determine if binary tree can be converted to another by doing any number of swaps of left and right child

Given a binary tree, write an efficient algorithm to determine if it can be converted to another binary tree by doing any number of swaps of its right and left branches.

For example, consider binary tree shown on the left below. It should be converted to binary tree shown on the right.

 
tree-nodes-swap
 


 
We can easily solve this problem by using recursion. We return true if

1. both trees are same or both trees are empty or

2. both trees are non-empty and value of root of X and Y are same and

(a) left subtree of X can be converted to right subtree of Y and right subtree of X can be converted to left subtree of Y.

(b) right subtree of X can be converted to left subtree of Y and left subtree of X can be converted to right subtree of Y.

 
C++ implementation –
 

Download   Run Complete Code

 
The time complexity of above solution is O(n) and need O(h) extra space for the call stack where h is the height of the tree.
 

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 🙂