What is the basics algorithm for testing if a tree is symmetrical. Because it is a binary tree, I would assume that it would be a recursive definition of sorts
The formal question is below:
A binary tree is a mirror image of itself if its left and right subtrees are identical mirror images i.e., the binary tree is symmetrical. This is best explained with a few examples.
1
/ \
2 2
TRUE
1
/ \
2 2
\
3
FALSE
1
/ \
2 2
/ \ / \
4 3 3 4
TRUE
1
/ \
2 2
/ \ / \
3 4 3 4
FALSE
1
/ \
2 2
/ \
3 3
TRUE
In a programming language of choice, define a BTree class/C struct and an associated method to check if the tree is a mirror image. For statically typed languages, you can assume that node values are all integers.
Class/structure definition
BTree {
BTree left;
BTree right;
int value;
}
Assume that the root of the tree is tracked by caller and function isMirror() is invoked on it.
Also, if defining a class, make sure to provide a no-argument constructor and getter/setter methods if data elements are not publicly accessible.
How about calling mirrorEquals(root.left, root.right) on the following function :-
boolean mirrorEquals(BTree left, BTree right) {
if (left == null || right == null) return left == null && right == null;
return left.value == right.value
&& mirrorEquals(left.left, right.right)
&& mirrorEquals(left.right, right.left);
}
Basically compare the left subtree and inverted right subtree, drawing an imaginary line of inversion across root.