JS Algorithm Problem: Symmetric Tree
“Given the root of a binary tree, we will check whether the binary tree is a mirror of itself (i.e., symmetric around its center).”
-LeetCode
Example 1:
The binary tree’s is also represented with the root being an array.
root = [1,2,2,3,4,4,3]
For this example, the binary tree is symmetrical mirror image. So it will have the output is true.
Example 2:
In our second example, we have a binary tree that is not symmetrical from the center.
root = [1,2,2,null,3,null,3]
The output is false.
The Approach:
We start off with the function isSymmetric, we have to return what we will find out if the tree is a mirror image. So we create a isMirror function that takes in the parameters of two root’s because in a binary tree we have to look at the two sub trees (left and right) that are branched off from the parent node. We will call the sub trees as tree1 & tree2. We pass tree1 and tree2 as our parameters. In our first if statement, we will start with the base case if tree1 and tree2 are both equal to null, then we will return true. The second if statement will be if tree1 or tree2 are either equal to null, then we can determine both sides are not symmetrical. Last we will return tree1 & tree2 and the determination of the sub trees left and right roots made possible from the definition for a binary tree node. We return tree1.right and tree2.left and tree1.left and tree2.right by calling the isMirror function and passing those two parameters respectively. This is because when we determining whether the trees are a mirror image, we have to compare tree side the opposite side of the other tree. After we complete our isMirror function, we have to make sure that we are calling the isMirror function within the isSymmetrical function and returning the answer from that function.
Tree Node
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
The answer:
var isSymmetric = function(root) {
return isMirror(root, root)
};
const isMirror = (tree1, tree2) => {
if(tree1 == null && tree2 == null){
return true
}
if(tree1 == null || tree2 == null){
return false
}
return (tree1 && tree2) && isMirror(tree1.right, tree2.left) && isMirror(tree1.left, tree2.right)
}
