Wynwood Walls, Miami
Given a Binary Tree, determine if it is symmetrical
Understanding the problem
A symmetrical binary tree is a binary tree whose left and right side of the root are symmetrical.
Solving it
A binary tree can be DFS traversed using simple recursion.
In the given problem, we have 2 subtrees - one on the left and one on the right.
We can simultaneously traverse both subtrees, node by node using the DFS algorithm and compare each node of both trees at the same time
Pseudo Code
isMirror ( leftMirrorNode , rightMirrorNode ) {
if ( leftMirrorNode == null && rightMirrorNode == null )
return true
return true
if ( leftMirrorNode == null || rightMirrorNode == null )
return false
return leftMirrorNode.val == rightMirrorNode.val
&&
isMirror ( leftMirrorNode.left , rightMirrorNode.right )
&&
isMirror ( leftMirrorNode.right , rightMirrorNode.left )
}
}
main (root) {
return root != null AND isMirror( root.left, root.right )
}