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.

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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Data structure to store a Binary Tree node struct Node { int data; Node *left, *right; }; // Function to determine if two given binary trees can be transformed // to each other by doing any number of swaps of left and right subtree bool equal(Node* X, Node* Y) { // base case: both trees are same //(handles the case when both trees are empty) if (X == Y) return true; return (X && Y) && (X->data == Y->data) && ((equal(X->left, Y->left) && equal(X->right, Y->right)) || (equal(X->right, Y->left) && equal(X->left, Y->right))); } |

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 🙂

## Leave a Reply