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.
We can easily solve this problem by using recursion. We return true if
2. both trees are non-empty and value of root of X and Y are same and
(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 –
// Data structure to store a Binary Tree node
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 (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.