Foldable binary tree
Problem: A binary tree is foldable if it's a mirror image of itself
i.e. if its left and right subtrees are identical mirror images
Example:
1
/ \
2 2
/ \ / \
4 3 3 4
Foldable
1
/ \
2 2
/ \ / \
3 4 3 4
Not foldable
1
/ \
2 2
/ \
3 3
Foldable
Solution:
boolean isFoldable(Tree left, Tree right)
{
if (left == null && right == null)
return true;
if (left == null || right == null)
return false;
return
left.value == right.value &&
isFoldable(left.left, right.right) &&
isFoldable(left.right, right.left);
}
|
