Given a binary tree,find whether it can be foldable or not :
A tree can be folded if left and right subtrees of the tree are structure wise mirror image of each other. An empty tree is considered as foldable.
Algorithm : we can do this using recursion.
1.If the root is null,then it is foldable.
2.else check left and right branches recursively.
recursion function :
if left and right both are null,then return true.
if one branch is null while other branch is not null,return false.(asymmetric)
Do the same thing for left and right branches.
Refer : http://geeksforgeeks.org/?p=7956
A tree can be folded if left and right subtrees of the tree are structure wise mirror image of each other. An empty tree is considered as foldable.
Algorithm : we can do this using recursion.
1.If the root is null,then it is foldable.
2.else check left and right branches recursively.
recursion function :
if left and right both are null,then return true.
if one branch is null while other branch is not null,return false.(asymmetric)
bool isFoldable (node* root) {
if (!root) return true;
return areMirrorImages(root->left, root->right);
}
bool areMirrorImages (node* leftTree, node* rightTree) {
if (!leftTree && !rightTree)
return true;
if (!leftTree && rightTree)
return false;
if (!rightTree && leftTree)
return false;
return areMirrorImages (leftTree->left, rightTree->right) && areMirrorImages (leftTree->right, rightTree->left);
}
Refer : http://geeksforgeeks.org/?p=7956
Iterative method :
ReplyDeleteJust dfs for the left subtree and log all events (left, right childs and elements) - use stack for this.
Then do the same for the right subtree, but check events in a reverse (left child event should be right child).
If there are no differencies, so right subtree is an exact mirrot of the left one
thanks..
ReplyDelete